L’adattamento dei Cetacei alla vita in ambiente acquatico ha imposto, presupponendo una origine terrestre dell’ordine, enormi trasformazioni anatomiche.
L’origine del gruppo, quasi sicuramente polifiletico, rimane però incerta in quanto non si hanno alla base fossili che permettano di identificare collegamenti certi. È ipotizzabile che la base comune sia da ricercare in un gruppo di mammiferi terrestri mesozoici a caratteri generalizzati dei quali però mancano riscontri paleontologici.
L’ordine dei Cetacei è diviso in tre sottordini: Archeoceti esclusivamente fossili, Odontoceti e Misticeti, con rappresentanti fossili ed attuali.

Negli anni Ottanta viene ritrovato in Pakistan il più antico resto attribuito agli Archeoceti (Pakicetus) in terreni dell’Eocene basale (circa 55 milioni di anni fa). Questo rinvenimento anticipa di diversi milioni di anni la presenza sicura dei Cetacei ancestrali; le caratteristiche anatomiche degli scheletri presentano ancora caratteri misti, in parte riconducibili a quelli di forme terrestri.

Seguono i più avanzati Archeoceti dell’Eocene medio-superiore (Basilosauridae) che vissero e si svilupparono dal Luteziano inferiore (Eocene medio) per oltre 15 milioni di anni. Già nelle forme del Luteziano inferiore dell’Egitto (Protocetus) sono presenti caratteri tipici di un adattamento alla vita marina: corpo allungato, assenza di arti posteriori visibili all’esterno, arti anteriori molto corti. Permangono tuttavia caratteri, quali ad esempio la disposizione di alcune ossa del cranio, la dentatura eterodonte (formula dentaria: 3/3, 1/1, 4/4, 2 o 3/4), le sette vertebre cervicali libere, che non differiscono da quelli degli altri mammiferi coevi. Poche sono comunque le testimonianze fossili e provengono principalmente dal Subcontinente indiano, dal Nord Africa e dalle zone sudorientali del Nord America.
Nell’Oligocene compaiono gli altri due sottordini: gli Odontoceti e i Misticeti, le cui differenze sono tali che oggi si tende ad accettare l’ipotesi di una evoluzione separata da forme ancestrali terrestri distinte.
Gli Odontoceti si evolvono in diversi gruppi, tra i più importanti è da ricordare quello degli Squalodontidi vissuti nell’Oligocene e nel Miocene inferiore: in essi sono presenti caratteri di transizione tra gli Archeoceti e gli Odontoceti.
Nel Miocene si sviluppano i Delfinoidei e già 10 - 11 milioni di anni fa sono presenti gli antenati degli attuali delfini, narvali, beluga ecc.
Sempre alla base del Miocene compaiono anche i Fiseteridi (capodogli) e gli antenati delle attuali forme di acqua dolce (platanista del Gange e inia del Rio delle Amazzoni).

Le più antiche testimonianze fossili di Misticeti provengono da sedimenti oligocenici della Nuova Zelanda e del Nord America (Aetiocetus dell’Oligocene superiore dell’Oregon). I Misticeti fossili, differenziatisi poi nel Miocene in due famiglie (Balaenidae e Balaenopteridae), erano tra l’altro caratterizzati anche da grande variabilità dimensionale: sono stati trovati resti di forme non più lunghe di tre metri.

Dal Miocene superiore i ritrovamenti di Odontoceti e Misticeti si fanno copiosissimi; soprattutto nei sedimenti marini del Pliocene è relativamente frequente il rinvenimento di resti di cetacei.