De eldste kjente haiene stammer fra devon. De hørte til urhaiene, ordenen Cladoselachidae, som omfatter de mest primitive haier vi kjenner. De hadde ikke utviklet virvellegemer, så ryggstrengen (chorda dorsalis) var kraftig. Munnen var forrest på snuten, og de parede finnene var trekantede og med bred basis mot kroppen. Gattfinnen manglet, den store halefinnen var (som hos nålevende haier) usymmetrisk, heterocerk.
En rekke slekter av primitive haier er kjent fra yngre paleozoikum og eldre mesozoikum. Ferskvannshaiene i ordenen Pleurocanthodii levde i karbon og perm. De hadde en kraftig pigg på nakken, nærmest kvastformede parede finner og totakkede tenner. Slike tenner er kjent fra bl.a. permavsetningene i Asker.
De moderne haiene dukket først opp mot midten av mesozoikum, og er i alt vesentlig kjent på tenner. Representanter for slekten Carcharodon (samme slekt som den nålevende hvithaien) fra tertiær hadde tenner på opptil 15 cm, og selve haien var antakelig over 20 m lang.