Les premiers restes de Cristatusaurus furent récoltés en 1973 par le paléontologue français Philippe Taquet alors en mission paléontologique dans le désert du Ténéré. Il s'agissait de deux extrémités antérieures de prémaxillaires qui ont été décrites et identifiées de manière incorrecte à des extrémités de dentaires par Taquet en 1984. Toutefois, ces éléments ont permis à ce paléontologue de reconnaître pour la première fois l'existence d'un museau long et étroit chez les Spinosauridae. Les fragments crâniens ont ensuite été décrits une nouvelle fois par Kellner et Campos en 1996 qui les rapprochèrent à des prémaxillaires, puis par Taquet et Russel en 1998 qui décriront d'autres éléments crâniens et postcrâniens et nommeront grâce à ceux-ci l'espèce Cristatusaurus lapparenti.