在潤迅工作的最後那段日子裡，馬化騰過得並不輕鬆，或者說過得並不快樂。當時，他已經是潤迅的開發部主管，由於業務和市場的限定，他必須按照公司的要求將大部分精力放在傳呼業務上。相對地，他所提出的有關互聯網方面的開發建議卻得不到重視。
2010年4月，馬化騰在接受《中國企業家》採訪時說：「那個時候我開始思考互聯網能帶來什麼，因為當時在做傳呼，第一個想法就是把網絡傳呼這個概念引進來，通過互聯網來傳呼，把內部的系統接起來，當時以為這可以給傳呼業帶來一點高科技色彩，能夠延緩(傳呼業的衰落)，因為當時(公司包括整個傳呼業)壓力很大了。其實手機一開始出來，短信一普及，我就知道傳呼機肯定是完蛋的，就變成夕陽產業了。」
興趣不一定非要變成工作，但如果所從事的工作和自己的興趣相差太遠，也是讓人不舒服的。當時的馬化騰就經受了這種負面的體驗，而且他也意識到潤迅這樣的戰略規劃其實是背離了互聯網發展的大方向。
其實當時不光是潤迅缺乏戰略眼光，整個傳呼行業也沒有認清自身黯淡的前景，一時的繁華讓整個行業集體性地「失明」——喪失了必要的警惕意識和戰略眼光，因此沒有人及早地進行轉型，以至於市場的拐點降臨在2000年的時候，幾乎所有的傳呼公司都是一片慌亂，這才想起要開拓新的業務模式。到了2001年，傳呼業務逐步走向死亡，在2002年則全線隕滅。最終，一度風光無限的潤迅，將自己僅剩的一些客戶無償讓給了聯通。
除了傳呼行業的衰敗之外，還有一個外部因素影響著馬化騰對未來的決策，那就是當時的丁磊將用7個月寫成的網易免費郵箱以119萬元的價格賣給了廣州的飛華網。馬化騰敏銳地意識到，互聯網絕對是一座等待著有識之士去開發的「金礦」，而且機遇稍縱即逝，他不能再等待下去了！與此同時，馬化騰的朋友圈子中，也有人給了他自己出去幹事業的精神動力。當時有一個南京的網友，總能給馬化騰一些寶貴的建議和鼓勵，讓他堅定了創業的信念。
此時的馬化騰已經不再滿足於做一個「IT技工」了，他想要在更廣闊的領域中發揮自己的才幹，也想讓他頭腦中的一個個構想變成現實。當然，那時候他可能不會想到騰訊今天能有如此輝煌的成就和地位，其實他的創業想法很簡單：就是想不斷地在互聯網上探索出一條新路，以提升自身的價值。另外，他通過股票分析系統賺到了第一桶金，也由此在資本市場裡積累了一定的創業資金，有了相對豐厚的物質財富作為基礎。這樣，馬化騰就不必為了生計而奔波勞碌了，他能夠將更寶貴的時間和精力用在他熱愛的行業中。
曾經有一個傳聞說，馬化騰當時在潤迅提出了要開發一個類似於QQ軟件的東西，然而這個富有前瞻性的提議卻未能引起潤迅高層的關注，因為他們還無法認識到這樣一個小軟件能有什麼發展前景。當時雖然也進行了討論，不過讓大家感到疑慮的是，這樣的軟件到底收不收錢，如果收錢會有人買來用嗎？如果不收錢做它還幹什麼。
潤迅高層之所以有這樣的想法，是因為他們在當時還看不到客戶資料的重要性，而是將全部注意力放在了賺錢上。事實上，那些有著極高忠誠度的客戶才是商家最重要的資源和財富，不是能用錢來衡量的。也許正是因為這樣一個原因，馬化騰認識到了自己和潤迅是「道不同不相為謀」，所以才打定主意自己創業。
不過值得注意的是，馬化騰當時在潤迅並沒有顯出什麼特別之處，一些老員工在回憶他時，幾乎都用了「沒想到」「當年其實不起眼」這一類的詞彙來形容他，可見馬化騰在潤迅是一個很低調、很不顯山露水的人，或許這就是厚積薄發的一種個人魅力。
1998年10月，馬化騰正式向潤迅提交了一封辭職信。公司對於這樣一個人才的流失，自然是有些不捨，但最終也沒怎麼挽留就「放走」了馬化騰。
1998年，中國的互聯網進入到一個高速發展的時期，在這一年，張朝陽創辦的搜狐、周鴻禕創辦的3721，都讓活躍在IT界的有志之士感到興奮，他們紛紛投身創辦互聯網公司，準備在這個全新的戰場中一展身手。
馬化騰當然也不例外，儘管他對具體要開創的事業還沒有一個清晰的思路，但是大的方向已經確定了下來——傳呼和網絡。馬化騰之所以認定了這兩個目標，是他認為自己擁有了5年的網齡和相應的職業經驗，因此這些資本的積累會幫助他在這兩個方向上有所作為。
不過，單靠一個人創業肯定不行，他需要尋找一些志同道合的戰友。
第一個戰友是張志東，他是馬化騰在深圳大學的同學，兩個人同在計算機系學習。張志東畢業之後，去了華南理工大學攻讀計算機碩士學位，碩士畢業後又回到了深圳，在當時比較著名的黎明電腦公司工作，主要做深滬兩市的證券交易軟件。
黎明電腦公司在當時的IT業是一家赫赫有名的公司，它得到過茅道臨所代表的華登風險投資的支持，其創辦者鄧一明是深圳IT業的頭面人物之一，後來還幫助騰訊尋找資金支持。後來騰訊的12位個人股東之一的「天使投資人」劉曉松，也曾經在黎明電腦公司任職過。
張志東個子比較矮，長著一張圓臉，說話的時候總是面帶微笑，然而一旦和馬化騰爭論起有關技術的問題時，他就會顯得比較偏執甚至會臉紅脖子粗，所以熟悉他的人送給他一個「冬瓜」的外號。後來隨著騰訊的發展壯大，張志東的「冬瓜」的外號也變成了英文名Tony，這顯出了大家對他的喜愛和尊重。
張志東和馬化騰比較相似，也是一個技術型人才，當初兩個人在深圳大學唸書的時候，都是系裡技術拔尖的那一批人，而張志東又是尖子中的尖子，哪怕是將他放置於深圳的計算機發燒友中，也是數一數二的。而且，張志東同樣是個工作狂，除了計算機之外只有象棋這個愛好了。他在黎明電腦工作的時候就一直很努力，總是加班到深夜，而到了第二天凌晨還要繼續工作。
QQ的架構設計始於1998年，然而十多年過去了，用戶數量猛增，這個框架卻還很適用，足見張志東的技術水平非同小可，甚至說是高得難以想像。另外，張志東和馬化騰一樣，都是比較低調的人，當別的公司創始人紛紛買別墅、開遊艇的時候，他還只開著中檔車。後來，張志東身邊的人說，他從來不依靠這些物質上的東西來證明自己。
在馬化騰和張志東創辦騰訊後的一個月，騰訊的第三個創始人加入了，他就是曾李青。
曾李青本科就讀於西安電子科技大學，和柳傳志是校友。當時曾李青學的是通信，所以在畢業之後被分配到了深圳電信，一路走來比較平淡安穩。當時，深圳電腦協會會長的女兒和馬化騰、張志東都是從中學到大學的同學，而協會搞活動的時候，曾李青也經常被派出去參加，這樣就認識了同被邀請的馬化騰和張志東。
曾李青是當時深圳互聯網的領軍人物之一，他具有開拓者的魄力和勇氣，也是深圳甚至國內首個寬帶小區的推動者。當時這個項目是個系統集成項目，還差點夭折，不過曾李青還是憑著自己的努力完成了這個項目，而且是以類似做期貨的手段實現的，這在20世紀90年代絕對是讓人「高山仰止」的。
1998年的秋天，曾李青的事業遭遇到了低谷，他找到了當時深圳電信局局長許文艷，想讓對方給自己指點一下迷津——是回局裡好還是下海好。後來許文艷推薦他去找馬化騰，他這才加入了馬化騰的創業團隊。當時三個人還分了工：馬化騰負責戰略和產品，張志東負責技術，曾李青負責市場。
根據騰訊員工的描述，曾李青是騰訊五大創始人中「最好玩、最開放、最具激情和感召力的一個」，跟馬化騰的溫文爾雅、張志東的極客精神產生了鮮明的對比。在他成為騰訊COO之後，一次會議進行中忽然斷網了，技術人員也沒及時出現，曾李青竟然當著一群客戶和手下，自己鑽進桌子底下將線路接通了。
很多人第一次見曾李青的時候，會覺得他比馬化騰更像老闆，因為他比較富態，穿著上也更商務，在語言表達和人際溝通方面也十分擅長。所以每次他們出去，曾李青都會被外人誤認為是大老闆，面目清秀的馬化騰反而被當成了秘書或者助理。
除了他們三個之外，騰訊的另外兩個創始人是許晨曄和陳一丹。
許晨曄是馬化騰、張志東深圳大學計算機系的同學，他在從深圳大學畢業後進修了南京大學計算機應用專業的研究生，隨後來到了深圳電信數據分局工作，和曾李青曾是同事。許晨曄是一個性格隨和、有意見不輕易表達出來的人，是有名的「好好先生」。他最大的樂趣就是跟人聊天。陳一丹原名陳一舟，是馬化騰在深圳中學時的同學，後來他也進入了深圳大學，專業學的是化學。因為和另一個互聯網名人ChinaRen的創始者CEO陳一舟重名，所以他就索性改了個新名字叫陳一丹。陳一丹有律師執照，做事嚴謹，不過有時也不免有幾分張揚，總能在不同的時刻激發起大家的工作積極性。
四位戰友集齊了，他們是馬化騰在創業的道路上的左膀右臂，接下來就是和馬化騰一展宏圖、開疆擴土的時候了！