1998-1999年：Google出现和SEO理论的浮现
这一阶段，美国的互联网大会开始有一些关于网站优化的文章发表。这些文章开始关注到链接流行度（Link Popularity）、名录网站链接（Directory Listing）的意义。这段时间，搜索引擎也知道了需要限制人们的网站提交来防止垃圾网站的泛滥，于是开始组织反击。
Alta Vista开始大规模剔除含有“我们来优化”或者“我们来推广”这类文字的网页。SEO的实践者开始意识到，要破解搜索引擎的原理越来越难。在1999年将一个网站提升到前十名要比在1998年难上十倍。搜索引擎开始更多关注链接流行度的意义。
Google也在1998年收到了第一张十万美元的风险投资，搬出了斯坦福校园，正式命名为Google公司，域名也从google.stanford.edu变成google.com。这个新的搜索引擎衡量网站的重要性首次将链接流行度作为排名的标准之一。
1999年5月，英国的FAST公司推出ALLTheWeb搜索引擎。它的网页搜索可利用ODP自动分类，支持Flash和PDF文件搜索，支持多语言搜索，还提供新闻搜索、图像搜索、视频、MP3和FTP搜索，拥有极其强大的高级搜索功能。这么强大的功能使它成为最流行的搜索引擎之一。
这一阶段的初期，搜索引擎也开始了多元化的进程，开始设立多语种的网站，比如Alta Vista就率先开始了拉丁语的版本。台湾中正大学吴升教授所领导的GAIS实验室于1998年1月创立了OpenFind中文搜索引擎。它是最早开发的中文智能搜索引擎，号称能抓取全球最多的网页并开始进入英文搜索引擎。
1999年Google获得了两千五百万的资金，开始全力发展，并且已经在媒体处理50万次搜索，这个投资也使Google再次搬家到旧金山——硅谷地区较Palo Alto的城市。Google也开始结识合作伙伴，从AOL到Netscape不久，Google再次搬家到目前的全球总部依然是旧金山——硅谷叫Mountain View的城市。这时候的搜索一千年开始设法控制市场，广告广泛地出现在搜索引擎上。这引起了许多搜索者的反感，因为大家还是在用56KB modem上网，大量的广告使网站页面出现太慢。
Google发现了这个影响搜索步伐的致命的问题。简洁的网页设计使众人耳目一新，飞快地搜索速度更使得各个站主奔走相告，每个站主论坛都充满了对Google的极好评价，杂志的采访也是接连不断地对Google进行推荐，Google的全面演出就正式登台了。