Rozpoczął wówczas studia prawnicze na uniwersytecie w Kairze, jednak zrezygnował z nich po kilku miesiącach, gdy w 1937 otrzymał zgodę na podjęcie nauki w Akademii Wojskowej. Znalazł się w grupie 10% studentów wywodzących się z ubogich warstw społecznych i przez to zwolnionych z czesnego. W czasie studiów poznał innych słuchaczy o nacjonalistycznych i antybrytyjskich poglądach, z którymi tworzył następnie ruch Wolnych Oficerów: Anwara as-Sadata, Abd al-Latifa Baghdadiego, Abd al-Hakima Amira i Zakarijję Muhji ad-Dina. Po ukończeniu szesnastomiesięcznej nauki w Akademii został skierowany do służby w garnizonie w Mankabadzie. Panująca w armii atmosfera, nieudolność wyższych oficerów i korupcja były dla niego wielkim rozczarowaniem. Następnie służył w Chartumie, a przez krótki czas w wojskach brytyjskich w Libii.

Według własnych wspomnień Nasera, od 1942 działał w podziemnej organizacji oficerów, która przekształciła się następnie w ruch Wolnych Oficerów (jej regularne spotkania zaczęły się w 1944). Wzorem dla niego był gen. Aziz Ali al-Masri. Sam Naser szybko uzyskał w nieformalnej początkowo grupie wysoką pozycję dzięki uzyskaniu w 1943 etatu wykładowcy w Królewskiej Akademii Wojskowej.