真正激起马化腾创业激情的，是一位南京的网友，他给了马化腾很多鼓励和建议。经过多次思想斗争，1998年10月，马化腾向润迅公司递交了辞职信。那时候的马化腾心中隐约有一个方向，觉得自己未来的创业可以在寻呼和网络两大资源之间找到空间，有了大概的想法，马化腾就去找自己的合作伙伴，他第一个想到的就是张志东。马化腾告诉张志东，他想把寻呼搬到互联网上去，网页寻呼、邮件寻呼和为呼台业提供互联网的扩展方案。张志东认为马化腾的想法很好，两人一拍即合，随后，他们又联系了陈一丹和许晨晔。四个昔日的好友重新聚在一起，对于马化腾的提议，他们三个没有太多犹疑就答应了。
1998年10月腾讯公司成立，公司的业务来源，成为腾讯公司几个创业元老共同关注的问题。有一天，马化腾和当时深圳数据通信局局长许文艳聊天，许文艳对马化腾谈起一个人，这个人是中国电信投资公司的市场部经理。许文艳隐约觉得此人应当对腾讯的发展有帮助，其中一个关键的原因是他很靠谱。马化腾经过一番打听，发现这个人自己也认识，他就是曾李青。谈及与腾讯团队的相识过程，曾李青感慨万千，“我一直都很感谢许文艳，当时我走至事业的低谷，感到很迷惘，她给了我真诚的建议，帮我做了正确的选择，并推荐我与马化腾团队认识，这才发生了我与腾讯的故事。”
曾李青与马化腾和腾讯的其他创始人一见如故。在决定一起创业后，他们进行了简单的分工，共同合作。后来腾讯的故事说明，曾李青不凡的营销能力，帮助腾讯度过了最困难的时期，不过这都是后话。腾讯最初的业务正是围绕网络寻呼展开的。马化腾和张志东携手，开始研发无线网络寻呼系统，这套系统的主要功能是让用户不必拨打电话，直接通过互联网将信息发送到寻呼机上。那时候的马化腾只是个睡沙发、吃盒饭的总裁，他与腾讯的创业“元老”一起挤在深圳赛格科技园4楼一间几十平方米的小厂房办公，不过那时候的腾讯公司，只有两个全职人员，马化腾和张志东；许晨晔、陈一丹和曾李青作为股东，在空闲时过来帮忙，因此，狭小的办公室还显得颇为宽敞。那时候马化腾的名片上没有出现过“总经理”的字眼，只印着“工程师”——马化腾当时的唯一期望，是公司能生存下来。这家十几个人的小公司的主要业务是为深圳电信、联通和一些寻呼台做项目，为了让这个草创初期的公司生存，腾讯公司还做网页、系统集成、程序设计。这些看似纷繁的业务，似乎与腾讯未来的主业没多大关系。
1999年2月，马化腾和张志东开发了中文OICQ。而在此之前的1996年，4位以色列人发明了IM的鼻祖——ICQ，那时它只是一个主要搞网上寻呼的“小玩意”。1998年，ICQ以一种星火燎原的态势风靡全球，用ICQ聊天在当时是一种时尚行为。而美国在线以2.87亿美金将ICQ品牌收购，这让很多公司看到了巨大的商机，包括中国电信这样的公司也在酝酿中文即时通讯项目，因为英文界面对大部分中国人来说是一个不低的门槛。不久，马化腾就在广州电信的信息港上看到了一个关于中文即时通讯项目的招标，尽管没有产品原型，但腾讯公司也制作了标书投标，结果投标失利。OICQ竞标的失败无疑是山重水复。
