1996年1月，佩奇他们发明了一个叫做“Backrub”的简单搜索引擎。这个搜索引擎之所以叫“Backrub”，是因为它主要处理反向链接（Backlinks），依据反向链接来评估网站的重要性。随着从网上搜集的数据增加，计算机不够用了，他们千方百计地省钱，自己购买零部件组装机器，还在仓库里翻找没有人认领的计算机，计算机在塞满了盖茨楼360室之后，又塞满了佩奇的宿舍，宿舍就是Google最原始的数据中心。他们最困难的时候，花光了他们自己的万美元积蓄，走投无路之时，只好透支张信用卡，还接受了他们导师1万美元资助。这段难忘的经历把佩奇锻炼成为一个成本控制与并行计算的专家：通过集成和连接便宜的个人电脑部件可以做出性能优越的计算机处理系统。
1998年初，他们的搜索引擎已经搜集了2600万Web网页。最初的Backrub搜索速度很慢，普通的搜索往往需要几秒甚至是十几秒钟才能完成。尽管Backrub有缺点，但是其搜索质量赢得了很多用户的青睐。依靠人们口耳相传、电子邮件和即时信息来向朋友们推荐，Backrub像病毒传播一样迅速广泛传播，Backrub请求量大幅上升。这个最初只有几个人知道的Backrub不知不觉地在斯坦福大学流行开来，成千上万的人开始使用它。除了质量不错外，Backrub的界面也很有特色，干净、清新，Google主页以白色为背景，只使用最基本的色彩，它的干净简单在当时以豪华缤纷为主流的互联网世界上显得是那么特立独行。
为什么Backrub会比其他搜索引擎的质量更好呢？幕后秘密是佩奇发明的独特的Pagerank算法。
说起Pagerank算法本身，也有一段不寻常的故事。布林和佩奇本来只对学术有兴趣，对开公司毫无兴趣，希望Pagerank算法能够卖点钱支付学术研究的费用，追随他们父辈的足迹，继续完成在斯坦福的学业。1998年3月，急需金钱的布林和佩奇找到他们的校友Altavista的设计者之一保罗?弗莱厄蒂，希望Altavista付100万美元购买即将获得专利的Pagerank算法，当时Altavista占据了整个搜索市场份额的54%，佩奇与布林认为Altavista需要改进自己的搜索技术。当时布林和佩奇信心十足，因为他们认为这个算法比Altavista要优越得多，速度快得多：如果打印出Altavista的数据库，要堆9650米高，Google搜索引擎可以在不到半秒钟的时间内从这个数据大海中找出任何一个词。但是结果令人失望，Altavista考虑再三，最终还是决定拒绝Google。Altavista的母公司数字设备公司（DEC）不希望在技术上仰仗外人，更为重要的是，Altavista认为搜索市场根本没有前途。这让布林和佩奇感到十分沮丧，在斯坦福大学专利办公室的帮助下，又找到Excite以及其他一些搜索引擎公司，这些公司拒绝买下Pagerank技术。这些公司当时普遍不看好搜索引擎市场，考虑的不是提升搜索技术，而是如何进行市场推广，扩大收入。最后，他们不得不找到雅虎，当时雅虎主要依靠人工编辑的地址目录来搜索网络，自己并没有搜索技术，依赖购买Inktomi的后台搜索技术服务。可是，雅虎最后也拒绝购买Google技术，因为Yahoo希望用户更多用自己的分类目录，而不是搜索。事实证明，雅虎也错过了历史上最划算的买卖。
