隻要英國人還占據著蘇伊士運河，埃及就不可能是一個真正的獨立主權國家。新生的革命政權在鞏固政治地位、發展國民經濟的同時，開始致力於英國撤軍以及與此相關的蘇丹問題的解決。
根據1889年1月英埃共管蘇丹協定，英埃兩國共同治理蘇丹，但實際上，英國獨攬蘇丹軍政大權，企圖將蘇丹從埃及管轄中分割出去，革命前，埃及對蘇丹的一貫立場是要求對蘇丹的主權，實現尼羅河流域的統一。“七·廿三”革命以後，埃及對蘇丹問題的態度有了轉變，革命政權確定了由蘇丹人自己解決主權問題的原則。承認隻有蘇丹人才有權為自己的國家選擇滿意的道路，應該立即讓他們自治，自己管理自己的事務。
1953年2月12日，英埃兩國簽定了“蘇丹協定”，決定蘇丹實行自治，確立了四條基本原則，一、結束英埃共管；二、蘇丹人有權決定自己的命運，或完全獨立或與埃及聯合；三、在自決之前的過渡時期內，蘇丹人自己治理蘇丹；四、保持蘇丹地區的統一。
在英埃“蘇丹協定”的指導下，11月1日，蘇丹議會按期舉行選舉，“民族聯合黨”大獲全勝。1954年1日，阿紮裏被任命為蘇丹總理，1956年1月1日，蘇丹議會決定蘇丹正式獨立。埃及政府馬上承認了蘇丹的獨立地位。
為了迫使英國從運河區全麵撤軍，埃及一方麵積極謀求通過外交談判，和平解決爭端，另一方麵也在擴充武裝力量，準備應付突發事變。1953年3月，納賽爾宣布：“如果我們的國家不能擺脫被占領的羈絆，我們將從政府中把革命領導人撤出來去領導人民發動抗英遊擊戰爭，我們將四處展開遊擊活動，使英國人感到他們為侵略我們的國家正在付出高昂的代價。”
4月27日，英埃開始談判。埃及堅決要求：英軍從運河區完全撤軍；軍事基地和軍事設施一並交由埃及政府管理；英國技術人員將在不超過幾個月的時間內為埃及技術人員所代替。由於雙方分歧太遠，談判未取得任何進展。8月，納賽爾訪問塞得港，號召軍隊要敢於戰鬥，勇於犧牲。他說：“為了使這夥強盜撤走，全埃及同你們戰鬥在一起，直至最後一名外國官員離開我們的祖國，埃及必須解放，占領軍必須撤離……這是一場關係到全體埃及人民的戰鬥，讓我們永遠團結一致，步伐整齊。”
此後，談判與衝突交錯進行著。1954年1月，納賽爾在經過冷靜地思考後，作出了戰略性讓步：他同意了英方在土耳其受到攻擊時，重新啟用運河基地的要求。從而為談判的發展掃清了障礙。10月19日，納賽爾同英國外交大臣納丁最終簽署了英國撤軍協定。該協定規定：廢除一九三六年條約；英軍在此後約20個月中分階段從埃及全部撤出；運河基地的現存設施在英軍撤出後由埃及掌管；基地至少要由1700名英國文職技術人員使用7年，在此期間，若出現對埃及或加入《阿拉伯共同安全條約》的任何一個阿拉伯簽定國及土耳其的軍事進攻，英國軍隊有權重新使用基地。協定簽定後，納賽爾宣稱：“英埃關係中醜惡的一頁已經翻過去了，我們正書寫新的一頁……現在，英埃兩國沒有任何理由不進行建設性的合作。”
納賽爾在堅持大原則的前提下，通過有限的讓步換取了英國全麵撤軍的承諾，使英國在持續占領埃及72年之後，不得不打道回府。最後協定的簽署，有利於改善埃及同西方的關係。英國重新向埃及轉讓武器，美國提供了財政援助，這些無疑對鞏固新生埃及的地位是有幫助的。
但對於激進的民族主義者而言，納賽爾也許讓得太多了。他使埃及部分地同西方的中東防禦體係聯係起來，難以奉行完全中立的政策，甚至還讓出了蘇丹。1954年10月26日，納賽爾在亞曆山大的一次大規模群眾集會上作演講時，受到極端民族主義分子的槍擊。他努力控製住自己的情緒，站在那裏沒有動。他向群眾喊道：“請記住，如果我發生什麼意外，革命仍將繼續，你們每個人都是加麥爾·阿卜杜勒·納賽爾！”
1957年1月，納賽爾乘英法以三國侵略埃及之機，宣布廢除了1954年英埃協定，從而切斷了埃及同英國的最後一點兒聯係。
正如納賽爾自己所言：“我已經實現了‘七·廿三’革命的最大任務。72年來，我們的祖國受盡了苦難。為了祖國的兒女們，我使祖國擺脫了災難，成為一個光榮、可愛和強大的國家。”