وفى عام 1939 طلب جمال عبد الناصر نقله إلى السودان، فخدم في الخرطوم وفى جبل الأولياء، وهناك قابل زكريا محيى الدين وعبد الحكيم عامر. وفى مايو 1940 رقى إلى رتبة الملازم أول.
عبد الناصر مع الحامية المصرية بالسودان
لقد كان الجيش المصري حتى ذلك الوقت جيشاً غير مقاتل، وكان من مصلحة البريطانيين أن يبقوه على هذا الوضع، ولكن بدأت تدخل الجيش طبقة جديدة من الضباط الذين كانوا ينظرون إلى مستقبلهم في الجيش كجزء من جهاد أكبر لتحرير شعبهم. وقد ذهب جمال إلى منقباد تملؤه المثل العليا، ولكنه ورفقائه أصيبوا بخيبة الأمل فقد كان معظم الضباط "عديمي الكفاءة وفاسدين"، ومن هنا اتجه تفكيره إلى إصلاح الجيش وتطهيره من الفساد. وقد كتب لصديقه حسن النشار في 1941 من جبل الأولياء بالسودان: "على العموم يا حسن أنا مش عارف ألاقيها منين واللا منين.. هنا في عملي كل عيبي إني دغرى لا أعرف الملق ولا الكلمات الحلوة ولا التمسح بالأذيال.
خطاب عبد الناصر لحسن النشار عن وضع الجيش فى جبل الأولياء فى السودان
شخص هذه صفاته يحترم من الجميع ولكن.. الرؤساء. الرؤساء يا حسن يسوءهم ذلك الذي لا يسبح بحمدهم.. يسوءهم ذلك الذي لا يتملق إليهم.. فهذه كبرياء وهم شبوا على الذلة في كنف الاستعمار.. يقولون.. كما كنا يجب أن يكونوا. كما رأينا يجب أن يروا.. والويل كل الويل لذلك... الذي تأبى نفسه السير على منوالهم... ويحزنني يا حسن أن أقول إن هذا الجيل الجديد قد أفسده الجيل القديم متملقاً.. ويحزنني يا حسن أن أقول أننا نسير إلى الهاوية – الرياء – النفاق الملق - تفشى في الأصاغر نتيجة لمعاملة الكبار. أما أنا فقد صمدت ولازلت، ولذلك تجدني في عداء مستحكم مستمر مع هؤلاء الكبار...". (خطاب عبد الناصر لحسن النشار..1941 ... ينشر لأول مرة) وفى نهاية عام 1941 بينما كان "روميل" يتقدم نحو الحدود المصرية الغربية عاد جمال عبد الناصر إلى مصر ونقل إلى كتيبة بريطانية تعسكر خلف خطوط القتال بالقرب من العلمين.
ويذكر جمال عبد الناصر: "في هذه المرحلة رسخت فكرة الثورة في ذهني رسوخاً تاماً، أما السبيل إلى تحقيقها فكانت لا تزال بحاجة إلى دراسة، وكنت يومئذ لا أزال أتحسس طريقي إلى ذلك، وكان معظم جهدي في ذلك الوقت يتجه إلى تجميع عدد كبير من الضباط الشبان الذين أشعر أنهم يؤمنون في قراراتهم بصالح الوطن؛ فبهذا وحده كنا نستطيع أن نتحرك حول محور واحد هو خدمة هذه القضية المشتركة".
وأثناء وجوده في العلمين جرت أحداث 4 فبراير 1942 حينما توجه السفير البريطاني – "السير مايلز لامسبون" – ليقابل الملك فاروق بسراي عابدين في القاهرة بعد أن حاصر القصر بالدبابات البريطانية، وسلم الملك إنذاراً يخيره فيه بين إسناد رئاسة الوزراء إلى مصطفى النحاس مع إعطائه الحق في تشكيل مجلس وزراء متعاون مع بريطانيا وبين الخلع، وقد سلم الملك بلا قيد ولا شرط.
ويذكر جمال عبد الناصر أنه منذ ذلك التاريخ لم يعد شئ كما كان أبداً، فكتب إلى صديقه حسن النشار في 16 فبراير 1942 يقول: "وصلني جوابك، والحقيقة أن ما به جعلني أغلى غلياناً مراً، وكنت على وشك الانفجار من الغيظ، ولكن ما العمل بعد أن وقعت الواقعة وقبلناها مستسلمين خاضعين خائفين. والحقيقة أنى أعتقد أن الإنجليز كانوا يلعبون بورقة واحده في يدهم بغرض التهديد فقط، ولكن لو كانوا أحسوا أن بعض المصريين ينوون التضحية بدمائهم ويقابلوا القوة بالقوة لانسحبوا كأي امرأة من العاهرات.
أما نحن. أما الجيش فقد كان لهذا الحادث تأثير جديد على الوضع والإحساس فيه، فبعد أن كنت ترى الضباط لا يتكلمون إلا عن النساء واللهو، أصبحوا يتكلمون عن التضحية والاستعداد لبذل النفوس في سبيل الكرامة.