Historiquement, le référencement dans les moteurs et annuaires était gratuit. Il s'agissait simplement de signaler l'existence d'un site, et l'indexation se faisait dans les jours, semaines ou mois qui suivaient.
Le modèle d'origine consistait donc à présenter le plus de résultats possibles.

Seulement, la démarche d'indexation, manuelle pour les annuaires et logicielle pour les moteurs, ont nécessité de plus en plus de ressources (temps, homme, machine), et il fallait définir un modèle pour la rentabilité des outils de recherche.
Le modèle payant pour les professionnels s'est donc largement développé, car les entreprises étaient prêtes à payer pour que le site soit évalué rapidement, car les délais d'attente devenaient trop longs à l'échelle de la vie d'une entreprise (plus de 6 mois sur Yahoo! en 1999).

La plupart des outils présentent aujourd'hui des formules de référencement payantes, mais il s'agit en fait d'évaluer le site de façon quasi immédiate (48 heures à une semaine).
Cela ne représente en rien une garantie de prise en compte, et que vous pourrez aller vous classer dans les catégories que vous désirez (pour un annuaire), ou que le site sera positionné en tête de file des résultats d'un moteur.

Certains sites sont reconnus pour leur impact, et le référencement payant peut être ... payant. Mais attention aux choix, et aux budgets, qui peuvent osciller de quelques euros (parfois moins de 2 €) à plusieurs dizaines d'euros par mois.

Il apparaît également sur de nombreux annuaires, l'option gratuite avec échange de liens, ou payant sans échange.

Il reste qu'aujourd'hui encore, les sites acceptant les soumissions gratuites sont parfois de bien meilleurs apporteurs de trafic qualifié que certains sites coûteux.