Google launched in 1998 into a crowded market. Searching the web was a solved problem by then, in the sense that several companies were doing it and none of them were doing it especially well.
The eight years before that are worth knowing about, partly as history and partly because the failures were interesting β most of these systems lost for reasons that had nothing to do with search quality.
Before the web: Archie and friends
The first search tool predates the web itself. Archie, built in 1990 at McGill University, indexed the file listings of public FTP servers. It did not read the files β it searched their names. If you knew roughly what something was called, Archie could tell you which server had it.
Gopher, a menu-driven system that competed with the early web, got its own search tools with the appropriately named Veronica and Jughead. All of these worked on structured hierarchies rather than pages, which made them precise and completely useless once the web took over.

The directory era
The first genuinely popular way to find things on the web was not a search engine. It was a directory: a hierarchy of categories, maintained by humans, into which sites were filed by hand. Yahoo began as exactly this in 1994, and for several years being listed in it was one of the most valuable things that could happen to a website.
Directories were excellent while the web was small and became impossible when it was not. Human editors cannot keep pace with exponential growth, and by the late nineties the category trees were badly out of date.
The crawler era
Automated crawlers arrived in 1994 and changed the shape of the problem. WebCrawler was first to index the full text of pages rather than just titles. Lycos came out of Carnegie Mellon the same year. AltaVista launched in 1995 out of Digital Equipment Corporation, ran on serious hardware, and for a while was plainly the best β it was fast, its index was enormous, and it supported real boolean operators.
Excite, Infoseek, HotBot and Ask Jeeves followed, the last of these built around asking questions in plain English, about fifteen years before that was technically feasible. Metasearch tools like Dogpile queried several engines at once, which tells you how inconsistent the results were.

Why they all lost
Two reasons, and the first is not the one people remember.
They stopped being search engines. The business model of the late nineties was the portal. Every major engine bolted on email, news, horoscopes, chat and shopping, on the theory that keeping users on the site was the goal. Search β which by definition sends people away β became a feature on a cluttered home page. Google’s famously bare front page was a strategic position, not a design preference.
Ranking by page content was gameable. Early engines largely ranked on what a page said about itself: keywords in the text, keywords in the meta tags. That is trivially manipulated, and by 1997 results for any commercial term were heavily spammed. PageRank’s insight was to rank on what other pages said by linking to you, which was much harder to fake at the time.
What is worth taking from it
Two things. First, the losing engines were not bad β AltaVista’s operator support was better than most of what you get now, and a lot of those operators still work. We covered the survivors in search operators that still work.
Second, the directory idea was abandoned because it did not scale, not because it was wrong. Human curation is still the best way to find small and strange sites, which is why it keeps being rebuilt by hand β see how to find weird websites yourself.
And if you want alternatives that exist right now rather than in 1996, try search engines that are not Google.