但是，納賽爾起初對敘利亞的建議並未表現出應有的熱情，盡管阿拉伯聯合是他夢寐以求的目標。那時，他的首要興趣是建立一條維護埃及與其他阿拉伯國家獨立自主、反對外來勢力幹涉的統一戰線，製定共同的政策。這種戰線以國家共同體的方式統一行動，而不是像敘利亞想象的那種超民族的同盟。這種主張反映了埃及作為一個單一民族國家的強烈的自我認同感。針對庫瓦特利的建議，納賽爾是這樣講的：“目前，我並不是按任何聯邦或邦聯製的思路在考慮問題……我比較喜歡諸如阿拉伯聯盟這樣的組織成為阿拉伯國家之間的強大且令人生畏的紐帶。”
不料，敘利亞國內危機的出現和隨後美國幹涉敘利亞內政的陰謀的暴露大大加快了埃敘聯合的步伐。1957年9月9日，納賽爾猛烈抨擊了美國的中東政策，並答應給予敘利亞無條件支持。在敘埃兩國進行了密切磋商後，10月10日，一小批埃及部隊在敘北部港口拉塔基亞登陸，與敘軍順利會師。這標誌著埃及已願意較多地卷入敘國內事務，並共同承擔防務義務。但是，一說到聯盟問題，納賽爾依然謹小甚微，這既與他一貫的審慎態度有關，也有複雜的國際形勢因素。他擔心在當時危機條件下，同敘利亞聯合，會使美國等國借口埃及吞並敘利亞而發動侵略戰爭。下麵這段對話很能反應當時納賽爾和敘利亞領導人的不同態度。
納賽爾說：“我知道憲法製度上的聯合不會是件容易事。……讓我們慢慢籌備這個聯合吧，這是一件很困難的事。”
敘利亞人問：“難道你要放棄自己早已宣布過的目標嗎？”
“沒有。但為了確有把握，我們還是打好基礎吧。”
“那麼，你的意圖是否任憑敘利亞遭到分裂和仇恨的蹂躪？難道你眼看著敘利亞滅亡嗎？”
“不。敘利亞是我的第二祖國。敘利亞是偉大的阿拉伯民族的一部分，我對該民族的未來滿懷信心。”
就在雙方還在為聯合的方式和進程難以達成一致時，風雲突變。納賽爾突然提出兩國完全合並，敘利亞像埃及那樣解散所有政黨，建立新的政治團體“全國同盟”取而代之，軍隊和政治相脫離等作為合並的前提條件。操縱時局的敘利亞軍方馬上接受了納賽爾的條件。以比茲裏為首的軍官們將全體內閣成員趕到了開羅。1958年2月1日，在兩國內閣的聯席會議上，通過了聯合方案，決定成立阿拉伯聯合共和國，納賽爾成為第一任總統。在三周後的公民表決中，埃及人和敘利亞人分別投了99.99%和99.9%的讚成票。在民眾的極度熱情中，阿聯正式成立。什麼原因使納賽爾最終下了決心呢？用他自己的話說就是“你們都知道阿聯當時是怎麼誕生的，敘利亞軍隊已分裂成不同的派別”，共產黨人認為“能壟斷敘利亞的日子已臨近，他們相信共產主義對敘利亞的滲透已強大到可能建成一個共產黨政府的程度。”
無論建立阿聯的最終動因是什麼，阿聯的誕生都具有十分重大的意義。納賽爾稱之為阿拉伯人自己創立的第一個國家，是由完全擺脫了外國控製的兩個國家組成的，是向阿拉伯解放的第一步。而就他自己而言，阿聯的出現是他在阻止美國妄圖“填補真空”的鬥爭中的轉折點。為了避免西方及中東親西方國家掀起反對新生阿聯的國際風暴，納賽爾表示“無論出現什麼樣的情況，阿拉伯人不打阿拉伯人”，阿聯是一個“排斥極端主義並不偏袒任何一方”的國家。
不久，納賽爾訪問敘利亞。看著街頭和房頂上歡聲雷動的群眾，他感到了比在埃及還要強烈的心靈震蕩，納賽爾不禁感慨萬千，“這是感情的狂潮在排山倒海般地奔騰”，“希望有一個包括所有國家的阿拉伯人民在內的包羅萬象的阿拉伯聯合”，“我們的責任是支持阿拉伯世界範圍內的阿拉伯民族，為把他們從帝國主義及其代理人手中解救出來而孜孜不倦地努力奮鬥”，這是“一項偉大的任務，其責任之重大足以叫人充滿敬畏”。以後，納賽爾不止一次地表示：在敘利亞這一“阿拉伯主義跳動的心髒”，感受到了“一生中最愉快的時光”。
埃敘兩國曾有過聯合的曆史，如在抗擊近東蒙古人和十字軍的時候。但如前麵提到的，兩國在政治、經濟、文化、曆史以及現實力量對比等方麵都不大相同。以政治觀念為例，敘利亞人崇尚個人主義而埃及人習慣於極權主義，僅這一點就給納賽爾出了難題。敘利亞和埃及並不接壤，它被土耳其、伊拉克、約旦及黎巴嫩等國包圍，這些國家當時都親西方，而對埃敘聯盟和納賽爾充滿敵意，很願意為搞垮阿聯出些力氣。埃敘間的陸路交通又被敵國以色列切斷，因此聯係起來很不便利。這些內外因素都對阿聯的發展起了不良影響。
阿聯的成立給中東各國和美蘇等大國的中東政策帶來了深刻的影響。1958年4月28日起，納賽爾對蘇進行為期三周的友好訪問。蘇聯經濟的發展、穆斯林宗教信仰自由以及蘇聯人對他隆重而熱情的接見，給納賽爾留下了深刻而美好的印象。他談到：“曆史經驗證明，蘇聯與我們的合作是建立在幫助我們鏟除勢力範圍並發展我們的經濟，使我國工業化這一真誠願望的基礎之上的。如果有人想奴役一個國家，他就不可能幫它發展實力，無論這種實力是在軍事方麵還是在工業發展方麵。”但事實上，蘇聯並非對阿聯無保留地支持，而是懷著喜憂參半的心情。敘利亞和埃及聯合，減少了它倒向西方陣營的可能，但共產主義在那裏的影響也被削弱了。納賽爾後來透露出了訪蘇時不和諧的一麵：赫魯曉夫要求納賽爾讓共產黨自由活動，納賽爾則認為這是對阿聯內部事務的粗暴幹涉。此後，赫魯曉夫在蘇共二十一大上又老調重彈。