尽管在朋友们的帮助下，马云已经陆续打开了钱江律师事务所、望湖宾馆以及杭州第二电视机厂等单位的市场，但是新的问题却又接踵而至。在起步阶段的4个多月中，马云销售的实际上还是一种在国内看不到的商品，仅凭几份美国寄来的打印纸和一个越洋电话是不可能让客户完全信服的。于是，就有人怀疑这些打印纸其实都是马云自己在电脑上制作出来的，而根本没有在网络上。甚至还有很多人怀疑马云根本就是个骗子，是在对客户进行诈骗的诈骗犯。于是，慢慢地马云就背上了“骗子”的骂名。对于“骗子”的骂名，马云很想为自己解释、澄清一下，但是，自己又能怎么解释呢？又怎么能解释得清楚呢？马云知道自己已是跳进黄河都洗不清了，因为当时的互联网在中国的确还没有几个人知道，因此，马云也只能默默忍受着这些压力，承担着骂名和怀疑。直到1995年7月，上海终于开通了互联网专线，马云也有了洗刷罪名、沉冤得雪的机会。
1995年8月的一天，在西子湖畔的一间民房里，马云弄来了一台486笔记本电脑，同时还找到望湖宾馆的总经理和杭州明珠电视台的新闻记者，他要当场向人们作一场现场演示，为自己洗刷冤屈。马云把摄像机对准电脑，然后从杭州打长途到上海互联网。因为当时的电脑还是拨号上网，网速非常慢，马云一干人足足等了三个半小时，网页才下载完毕，电脑屏幕上终于出现了望湖宾馆的企业主页。看到这些，客户兴奋了，记者兴奋了，所有在场的人都欢呼起来。那一刻，马云的眼泪夺眶而出，都说男儿有泪不轻弹，但是马云实在抑制不住激动的心情，也控制不了自己的喜悦，这次，他的罪名终于得到了洗刷，经过四个月的煎熬，他终于为自己赢回了清白。
让马云万万没想到的是，在自己刚刚洗去罪名的时候，他却碰到了真正的骗子。1995年下半年，有五个来自深圳的人突然找到马云，说他们愿意出资20万元做中国黄页的代理商，这个消息对马云来说无疑是救命稻草。于是，马云二话没说就立刻将公司的核心模式和技术全部告诉了他们，并专门派技术人员马不停蹄地赶到深圳昼夜不停地为他们创建了系统。看到马云的服务如此周到，这些代理商非常满意，并告诉马云三天后到杭州签合同。接下来，马云就开始日夜期盼着这笔大单，而且还开始憧憬美好的未来。但是，出乎意料的是，马云苦苦等了三天三夜，却什么也没有等来。后来，经朋友们的打听，马云才知道那几个深圳人刚刚开过了新闻发布会，拿出来的东西与中国黄页一模一样。此时，马云才知道自己上当受骗了。后来，马云在回忆这件事的时候说：“当时真的受不了，但我还是把它扛下来了。”
也许是上天故意要考验马云这个与众不同的年轻人，接着在他又遭受了更加残酷的打击。在马云从北京回来之后，中国黄页的经营又陷入了困境。1996年互联网开始成为各大媒体和企业关注的焦点，同时也成为了一种最有力的新经济的代表，马云的中国黄页也在这个时候遭遇到了许多的“强敌”。
当时，与马云的中国黄页竞争最激烈的就是杭州电信。可以说，这是一场实力相当悬殊的较量，当时的杭州电信注册资本是3亿多，而马云的中国黄页注册资本仅有2万；同时，这也是一场你死我活的较量，杭州就这么大的市场，正所谓“一山不容二虎”，杭州电信还有着非常好的社会资源和政府资源，马云却什么都没有。不仅企业觉得马云没有实力，就连民众也觉得马云就是名不见经传的杂牌军，根本没有人相信马云。除此之外，杭州电信还利用中国黄页已有的名声，做了一个和中国黄页名字很相近的网站--Chinesepage.com，并且也叫中国黄页，其目的就是要分割马云的中国黄页市场。为了拯救身处困境的中国黄页，马云决定先找一个靠山来增强自己的“抗击打”能力，马云最终决定与杭州电信合作。1996年3月，马云将中国黄页的全部资产折合成60万人民币，自己的团队占30%的股份，杭州电信再投入140万人民币，占70%的股份，开始了与杭州电信的合作。
从一开始，马云与杭州电信的合作就是一个无奈的选择，不久，双方的合作就出现了问题。虽然杭州电信也非常看好马云的中国黄页，但是他们急于把企业做大、赚大钱，对于这一点，马云则认为，做互联网公司就像养孩子，不可能让三岁的小孩子去赚大钱。因此，双方互相争执，分歧也越来越大，杭州电信身为大股东，自然有更多的话语权和决定权，于是，大家都开始闹情绪，先是何一冰要辞职，然后是中国黄页的全体员工要辞职，最后闹到马云也要辞职的地步，这个事件甚至惊动了当时的《人民日报》。
为了中国黄页的前途，各方面的人都想让马云回去，但是马云觉得非常委屈，认为自己辛苦打下的江山，如今却没有自己的立足之地。马云只好被迫与杭州电信分道扬镳，忍痛放弃了自己的心血--中国黄页。
在马云向和自己共同创业的兄弟宣布这个决定的时候，有人抱怨不甘心自己辛辛苦苦两年就这么完了；也有人觉得待在没有马云的中国黄页很没劲，也要跟马云一起走。马云对此也觉得心有不甘，但是马云最后还是狠着心说：“不行，中国黄页还有很长的路要走，你们要留下来。”同时，一向不在乎钱的马云还把当时自己所拥有的中国黄页的21%的股份全部送给了一起创业的员工，他之所以这样做，就是为了他们能为自己和中国黄页好好耕耘，获得更多的收获。
就这样，马云毅然离开了重组后的中国黄页，这也是马云人生中的第一次重大挫折和失败。后来，马云回忆说：“这些事太多太多了，每次的打击只要你能挺过来就会变得更加坚强。我又想，通常期望越高，结果失望就会越大，所以我总是想明天肯定会倒霉，一定会有更倒霉的事情发生，那么明天真的有打击来了，我就不会害怕了。你除了重重地打击我，又能怎样呢？来吧，我都扛得住。抗击打能力强了，真正的信心也就有了。所以我现在最欣赏两句话，一句话是丘吉尔先生对遭受重创的英国公众说的话"永不放弃"，另一句话是"满怀信心地上路，远胜过到达目的地"。”
中国黄页的失败其实也是马云的成功。可以这样说，如果没有中国黄页的经验积累，就不会有后来阿里巴巴的成功和辉煌。
二次进京，彷徨之后南下杭州
我给你们三个选择：第一，你们去雅虎，我推荐，雅虎一定会录取你们的，而且工资也会很高；第二，去新浪、搜狐，我推荐，工资也会很高；第三，跟我回家，只能分800块钱人民币，你们住的地方离我5分钟以内，你们自己租房子，没办法打出租车，没办法上下班，而且必须在我家里上班。走还是留，你们自己作决定。
--马云
任何人的成功都需要积累，都需要磨炼，这是一条恒久不变的真理。每个人只要有勇气，那么人生即使在零度以下也能够沸腾。马云在遭遇人生中第一次重大挫折之后，并没有因失败而掉眼泪，也没有失望、气馁。
马云在哪里摔倒就在哪里爬起来，而且是擦干眼泪再次前行。1997年，当马云离开中国黄页的时候，外经贸部对马云说：“到北京来吧，来这儿你能干得更好。”于是，马云便带着自己的创业团队重新回到了北京，并加入到了当时的外经贸部，继续开发网上贸易站点。就这样，马云在北京租了一个还不足20平方米的小房间开始没日没夜地工作，给外经贸部做网站，通过他的努力，外经贸部成为了中国第一个上网的部级单位，这包含了马云不小的成绩。
后来，外经贸部又另外成立了一家公司--中国国际电子商务中心（EDI），并由马云组建、管理，马云占了30%的股份，外经贸部占了70%的股份，不过，那时的马云实际上只有几千元的工资，其他什么都没有。长期以来，马云发现在政府的编制里很多事情都很难做，存在着许多说不清楚的问题。尽管那时提起马云与外经贸部的合作，人们都说他们是“中国的梦之队”，但事实上到底是怎么一回事就连马云自己也说不清楚，他整天都是“稀里糊涂”工作的。就在这种不清不楚的尴尬环境里，不甘心受人管制的马云天天都在思考一个问题：“我下一步该怎么走？”在外人看来，当时的马云所面临的无非就是两条路：一条是留在北京，另一条是离开北京。如果留在北京，机会倒是有，因为当时的新浪和雅虎都希望马云加入他们的团队，但是马云却认为北京的网络太浮躁，很难有所成就，况且马云也已经受够了在政府企业里做事时条条框框、陈规陋习的束缚。马云的直觉告诉自己：“中国的网络形式已经开始发生变化了，全世界的互联网高潮马上就会到来，如果自己不单干就对不起这千载难逢的大好机会。”于是，1999年，经过一番挣扎和思考之后，马云又一次作出了他人生中重大的决定：南下杭州，回老家自己重新创业！
就在马云作出这个决定的晚上，他将团队中所有的人聚集在一起。当初马云第二次北上的时候，是带着当年从创建中国黄页时期就跟着自己的八名伙伴一起出来的，现在，既然他自己要回老家重新创业了，那么他就觉得应该把他们都先安排好。听了马云要回杭州创业的决定后，几乎所有的人一下都惊呆了。按常理说，马云简直就是在瞎折腾，在北京干得好好的，还是在为政府部门做事，前途也一定不会太差，为什么还要再回去过那种苦不堪言的生活呢？
对此，马云也很理解伙伴们的想法，也知道自己的想法并非会被他们所接受。但是，马云还是诚恳地说：“我给你们三个选择：第一，你们去雅虎，我推荐，雅虎一定会录用你们的，而且工资也会很高；第二，去新浪、搜狐，我推荐，工资也会很高；第三，跟我回家，只能分800块钱人民币，你们住的地方离我五分钟以内，你们自己租房子，没办法打出租车，没办法上下班，而且必须在我家里上班。走还是留，你们自己做决定。”马云本来是打算给伙伴们三天时间考虑的，但是五分钟后，包括他妻子和五个患难与共兄弟在内的团队成员就一致决定跟着马云一起回杭州。那一刻，外表看来坚强的马云流泪了，他非常感动，心里有一股暖流在涌动，同时，他浑身也充满了力量。他在心里默默地告诉自己：“朋友们从来都没有对不起我，我也永远不会做对不起朋友们的事情，我们回去，一切从头开始，从零开始，重建一个我们这一辈子都不会感到后悔的公司。”
就这样，马云就带着自己的团队重新回到了杭州，重新踏上了创业的艰苦道路……
再别京城，洒下伤感的英雄泪
我在外经贸部的工作经验让我了解了许多中小企业的需求，也教会了我如何让互联网服务于世界和中国的中小企业，这的确对我帮助很大。
--马云
在马云宣布再回到杭州的时候，很多人都非常不理解马云的这一决定，也有很多人坚决反对他的这个决定。有些员工可能是因为年龄大了思想比较保守，因此不愿意让自己的生活再发生太多的改变，其中楼文胜就是极力反对回杭州的一个人，他觉得在北京挺好，为什么又要这么快抛弃刚刚有所成就的事业呢？对此，员工反应都很强烈。孙彤宇心里也很纳闷：“从终点又到起点，不断地创业、不断地漂泊，这是为什么呢？不管是从业务和业绩上看，还是从任何角度看，我们干得都不错，没有任何理由一定要重新开始呀！”
不管伙伴们有多么反对、多么不理解，但是到最后做抉择的时候，他们都没有任何犹豫，也不需要三天的考虑时间，五分钟后他们的抉择就出来了，那就是全部跟马云回杭州。
后来，彭蕾在回忆这件事的时候说：“马云给我们三天的考虑时间，我几乎没什么可考虑的，对于北京我没什么可留恋的，对于钱我也没有什么欲望，当初是一起来的，现在当然要一起回去了。”
由此可见，这是一个合作多年、相知多年、经历许多风雨的团队，是一个患难与共、情同兄弟的战斗集体，而且大家也都奔马云而来，奔事业和梦想而来。金钱诱惑不了他们，任何利益也拆不散他们。
马云和伙伴们流着眼泪南下杭州，在他们看来，这是既悲壮又迷茫的一件事。虽然在马云宣布回杭州的时候，没有一个人流泪，但是当他们要起身告别北京的时候，还是有人禁不住哭了，毕竟北京有着他们难忘的回忆和小有业绩的事业，相信对于任何一个人来说，这都是非常不舍的。
马云带着伙伴们举办了一个告别北京的宴会，他们喝起了北京的二锅头，大多数人都喝得半醉，从他们的表情上可以看见无奈和不舍，但同样也能看到他们的坚强和决心。他们谁都不相信会失败。席间，不知是谁带头唱起了《真心英雄》：“在我心中，曾经有一个梦，要用歌声让你忘掉所有的痛，灿烂星空，谁是真的英雄，平凡的人们给我最多感动……把握生命里的每一分钟，全力以赴我们心中的梦，不经历风雨怎么见彩虹，没有人能随随便便成功……”他们虽然是流着泪唱的，但也表明了他们对未来创业道路的坚定信心。这首歌是他们的真心流露，是他们对未来的信心。
在分别的时候，大多数人都黯然流泪。楼文胜看见马云也在流泪，但后来问起马云的时候他却不承认。宴会结束的时候，天已经很晚了，他们出来的时候竟然还下起了大雪，喝多了的谢世煌坐在路边，突然号啕大哭。往事也一幕幕地浮现在眼前：杭州创业，泪别中国黄页，北京创业，现如今又要泪别北京。他禁不住大吼：“从1995年奋斗到1998年，也该有所收获了，为什么我们还是这个样子？为什么还是这么迷茫？还是不知道路在何方？”这时，一位北京老大妈路过此地，就走过来拍拍谢世煌的肩膀说：“小伙子，别哭了，好姑娘多的是。”这句话让在场的人都哭笑不得。离开北京之前，马云和他的团队一共八个人去爬长城，在北京的一年时间，他们的生活几乎都是两点一线，根本没有出外游玩的时间，这还是他们来北京以后第一次爬长城。
当他们看到长城的砖墙上刻满了各种各样“××到此一游”时，马云说，这不就是BBS吗？我们的BBS要能做到这样就一切OK了。常言道：“不到长城非好汉！”如今爬上长城的他们还不能算是好汉，但他们发誓一定要成为好汉，谁也记不清他们都在长城上喊了些什么、说了些什么，但只有马云的一句话，至今让他们终生难忘：“要做一家中国人自己创办的全世界最好的公司！”