شهید محمدعلی رجایی در این دوران با فدائیان اسلام مرتبط شد و در سخنرانی های آتشین آنها که بصورت نیمه مخفی و گاه علنی برگزار میشد حضور مییافت. پس از دستگیری شهید نواب صفوی و یاران وفادارش وی با اینکه یک فرد نظامی بود به ملاقات نواب صفوی در زندان می رفت.
«با اینکه سرهای ما تراشیده بود که حکایت از نظامی بودن ما میکرد ولی ابایی از این نداشتیم که شناسایی و مجازات بشویم و به ملاقات سران فدائیان اسلام میرفتیم.»
«با فدائیان اسلام با اینکه در ارتش بودم و خطرناک بود همکاری میکردم، افکار آنها را خوب پسندیدم و در یک جمله میتوانم بگویم که آنچه امروز در بالاترین سطح فعالیتهای مذهبی مطرح میشود آن موقع فدائیان اسلام مطرح میکردند.»
«یک روز محمد تعریف میکرد وقتی من سرنگهبان میشدم چون میدیدم همدورهایهای من در آسایشگاه قمار بازی میکنند و به نصیحت من مبنی بر ترک این فعل حرام توجهی ندارند برای اینکه عملاً مانع کار حرام آنها بشوم زودتر از وقت مقرر خاموشی آسایشگاه را اعلام میکردم .»
درابتدای خدمت به دلیل صداقت و اطمینانی که در او مییافتند وی را به نظارت بر کار آشپزخانه گماشتند.
«بعضی افراد که دست های ناپاکی داشتهاند از او میخواستند در ازای دریافت مبلغ زیادی در برابر سوءاستفاده آنها در حیف و میل اجناس مربوط به آشپزخانه سکوت کند، ولی او دست رد بر سینه آنها زد و آن مبلغ زیاد را نپذیرفته و با دقت هر چه تمامتر بر کار خود پافشاری نموده است.»
در آخرین سال خدمت وقتی با ۲۰۰ نفر از همدورهایهای خود به نیروی زمینی(پادگان جی) منتقل گردید به دلیل اعتراض به این انتقال اجباری از خدمت در نیروی هوایی و ارتش استعفا داد .
دوران ۵ سالهای(۱۳۳۳ ۱۳۲۸) که شهید رجایی به عنوان یک درجه دار در نیروی هوائی ارتش خدمت میکرد مصادف بود با شکلگیری نهضت مقاومت ملی ومبارزات مردم مسلمان ایران به رهبری آیت الله ابوالقاسم کاشانی و جریان نهضت ملی شدن نفت که دکتر محمد مصدق سکاندار آن بود و نیز فعالیت مستمر و ترورهای انقلابی فدائیان اسلام که منجر به دستگیری و محاکمه و شهادت آنان گردید.
در این ایام شهید رجایی به طور مستمر در مسجد هدایت که در جلسات سخنرانی آن، شخصیتهای دینی سخنرانی میکردند و کسانی مانند دکتر یداللهسحابی، مهندس مهدی بازرگان و دیگر سران نهضت مقاومت ملی به عنوان شنونده در جلسات تفسیر قرآن مرحوم آیتالله طالقانی حضور داشتند شرکت داشت و از همین رهگذر بود که در سطح بالاتری از جریانات سیاسی وارد گردید.
«در بازگشت مرحوم آیت الله کاشانی به تهران که جمعیت زیادی برای استقبال ایشان به فرودگاه مهرآباد رفته بودند و بازار تهران هم به همین مناسبت بکلی تعطیل شده بود، من و آقای رجایی نیز از جمله کسانی بودیم که در فرودگاه حضور داشتیم.»
آنگونه که از متن اسناد ساواک استفاده میشود، وی در جریان ملی شدن نفت از آنجایی که این حرکت را یک حرکت ضد استعماری و ضد انگلیسی میدانست، از کسانی بود که راه مصدق را تأیید میکرد. این علاقه سالها پس از درگذشت دکتر مصدق ادامه داشت و طبق اسناد ساواک وی از جمله کسانی بود که در بعضی از سالها برای بزرگداشت سالگرد مرگ او به احمدآباد میرفت.
همزمان با این ایام مبارزات مردم مصر به رهبری جمال عبدالناصر در حال گسترش است که شهید رجایی نیز با روحیه پرشوری که داشت اخبار این نهضت را تعقیب میکرد. وی آنگونه که در متن بازجوئی هایش آمده است از مرگ جمال عبدالناصر به شدت متأسف و برای تسکین خود در سفارت مصر درتهران حضور یافت و دفتر یادبودی را که به این منظور تهیه شده امضا نمود.
