為了使中國黃頁繼續活下去，馬雲決定傍一個靠山，來增強自己抗擊風險的能力，最後選定同杭州電信合作。1996年3月，中國黃頁將資產折合成60萬圓人民幣，占30%的股份；杭州電信投入資金140萬圓人民幣，占70%的股份。
應該說馬雲當時有極好的機遇。第一，中國黃頁畢竟是中國第一家互聯網企業，占有絕對的先機；第二，中國互聯網產業起步雖晚但市場巨大；第三，中國黃頁一啟動就找到了一種成功的盈利模式。
但後來發生的許多事情讓馬雲始料未及。馬雲的戰略目標是打造中國的雅虎，為此製定了一係列品牌培育策略，但杭州電信卻有一套急功近利的經營策略。對此馬雲曾說：“做‘.COM’公司如同養孩子，你不可能讓三歲小孩去掙錢吧！” 雙方的裂痕愈來愈深，幾個月後，合作終於走到了破裂的邊緣。
1997年，馬雲不得不離開重組後的“中國黃頁”，這是他一生中的第一次“滑鐵盧”。
在離開中國黃頁之後，馬雲帶了5個年輕人，去了當時的外經貿部，在其所屬的中國國際電子商務中心（EDI）出任信息部總經理，馬雲占30%的股份、外經貿部占70%的股份，但實際上馬雲一個月就幾千圓的工資，其他什麽也沒有。馬雲還是很滿足，他租了一間不到20平方米的小房間，沒日沒夜地幹活，給外經貿部做站點，讓外經貿部成為了中國第一個上網的部級單位。後來成功建設了國富通、中國商品交易市場等網站。
日子一久，馬雲發現在政府的編製裏做事要受到許多限製，存在著種種說不清道不明的問題。怎麽辦？馬雲陷入了進退兩難的境地。留在北京嗎？機會倒是有，新浪和雅虎都希望馬雲去加盟，但馬雲發現在北京做事人心太浮躁，很難做成一件事。思來想去，馬雲決定還是回杭州發展。