Ako počet stránok na Internete vzrástol v neskorých 90. rokoch, vyhľadávače sa začali objavovať, aby pomohli ľuďom nájsť rýchlo informácie. Vyhľadávače rozvinuli obchodné modely na financovanie svojich služieb, ako PPC (Pay Per Click) programy, ponúkané spoločnosťou Open Text v roku 1996 a potom Goto.com v roku 1998. Goto.com neskôr zmenila svoj názov na Overture v roku 2001 a bola kúpená spoločnosťou Yahoo! v roku 2003 a teraz ponúka platené vyhľadávanie príležitostí pre inzerentov cez Yahoo! Search Marketing. Google aj začala ponúkať reklamu na stránkach výsledkov vyhľadávania v roku 2000 prostredníctvom programu Google AdWords. Do roku 2007, pay-per-click programy dokázali byť primárne zdroje peňazí pre vyhľadávače.
Poradcovia optimalizácie pre vyhľadávače rozšírili svoju ponuku na pomoc podnikom aby sa dozvedeli o využití reklamných príležitostí ponúkaných vyhľadávačmi a objavili sa nové agentúry so zameraním predovšetkým na marketing a reklamu pomocou vyhľadávačov. Pojem "Search Engine Marketing" navrhol Danny Sullivan v roku 2001 na pokrytie spektra činností spojených s výkonom SEO, správy platených výpisov vo vyhľadávačoch, predkladanie stránok do adresárov a rozvoju on-line marketingových stratégií pre podniky, organizácie a jednotlivcov.