Search is not a good business. Ad sales over top of search turned out to be. AdWords is the thing that catapulted Google towards (insane) profitability. And for the first few years, Google didn't really sell ads, or market themselves as even aiming to sell ads. But AdWords could only be successful because they had already captured the market on search, and so had a captive audience to show ads to (and relevance information based on their searches).
AdWords rolled out in 2000. Many of us had been using Google as a search engine since before the company had even been founded (1998).