Google started as a search engine. Their results were accurate and there were no ads. Gradually they started doing ads on search results, related to the search itself. This was better than what many of the competitors at the time were doing, which was for paid searches to be at the top.

Gradually Google became more and more an ad company. In 2007 they bought DoubleClick that was one of the leading ad companies on the Internet. This was part of them moving towards providing ads not only on search results, but on sites as well. At the time most ads were site or context sensitive.

So Google has been making money off ads for a long time. More or less from the beginning. The big change, however, was the move to surveillance-based ads, where the ads depends not on the site or page you are viewing, but on the person viewing the ad. That is where it went all wrong.