Le genre Spinosaurus est présent dans toute l'Afrique du Nord puisque des restes attribués à ce théropode ont été découverts avec certitude au Maroc, en Algérie, en Tunisie, au Niger et en Égypte. Les plus anciens restes avérés proviennent actuellement de l'Albien inférieur de la Formation de Chenini située dans la région de Tatahouine au sud est de la Tunisie et furent attribués à l'espèce S. aegyptiacus. Le matériel découvert dans les roches de Gara Samani en Algérie et associé à l'espèce S. maroccanus est également daté de l'Albien. La totalité des restes de Spinosaurus découverts au Maroc (Continental Intercalaire, Continental Red Beds ou encore Kem Kem Beds), en Égypte (Formation de Bahariya) et au Niger (Formation d'Echkar) sont datés du Cénomanien, voire plus précisément du Cénomanien inférieur.
Du matériel associé sans certitude au genre Spinosaurus sp. a été reporté en Libye dans des roches provisoirement datées du Tithonien-Néocomien, ainsi qu'au Kenya dans les Turkana Grits datés du Turonien-Santonien. Ce matériel n'a cependant pas été réétudié et redécrit dans la littérature scientifique depuis lors.
Les premières découvertes de Spinosaurus remontent au début du XXe siècle lors de l'expédition paléontologique allemande commanditée par le paléontologue Ernst Freiherr Stromer von Reichenbach et secondée par son collecteur de fossiles Richard Markgraf. C'est au printemps 1912 que ce dernier découvre et déterre une série d'ossements ensevelis sous 30 centimètres de grès et un mètre d'argile dure. Selon les écrits de Stromer, le site fossilifère se situe à quelques kilomètres au nord de Gebel el Dist, petit village de la vallée de Baharija (ou Bahariya) se trouvant dans le Nord de l'Égypte et à l'ouest du Nil. Les ossements dégagés comprennent entre autres une mandibule dépourvue de son extrémité postérieure, une dizaine de dents individuelles, des côtes incomplètes ainsi que des vertèbres cervicales, dorsales, sacrales et caudales. Ernst Stromer, à l'époque de la découverte, est revenu d'Égypte depuis un an et Markgraf fait ainsi parvenir les nouveaux ossements au paléontologue allemand qui travaille alors dans son bureau de l'Académie des Sciences de Munich. Le 6 novembre 1915, Stromer présente le résultat de ses recherches égyptiennes dans les comptes rendus de l'Académie Royale des Sciences de Bavière où il décrit et illustre par deux grandes planches les ossements d'un tout nouveau dinosaure qu'il nomme Spinosaurus aegyptiacus.
En 1934, le paléontologue décrit de nouveaux restes fragmentaires comprenant des vertèbres cervicales, dorsales et caudales ainsi que des os des membres postérieurs (tibia, fémur et phalanges du pied) qui proviennent également du site égyptien de Baharija. Il rapproche ces ossements à Spinosaurus mais, du fait de sa plus petite taille et de plusieurs différences morphologiques avec l'espèce aegyptiacus, il nomme ce nouveau spécimen « Spinosaurus B ». Selon certains scientifiques, les os de ce dernier n'appartiendraient cependant pas à un seul et même individu puisque les vertèbres seraient celles d'un dinosaure large et corpulent tandis que les os des membres viendraient plutôt d'un théropode large mais gracile. « Spinosaurus B » n'est actuellement plus considéré comme un Spinosauridae et les ossements rapportés à ce genre appartiendraient à un théropode d'une autre famille (Bahariasaurus ?) voire à un ornithopode.
La totalité des ossements de l'holotype de Spinosaurus aegyptiacus ainsi que ceux du théropode « Spinosaurus B » furent détruits lors d'un raid aérien des bombardiers de la British Royal Air Force sur Munich dans la nuit du 24 au 25 avril 1944. Le bombardement endommagea sévèrement le bâtiment qui hébergeait le Paläontologische Staatssammlung München et détruisit une grande partie de la collection de Stromer qui provenait d'Égypte. Deux photos des ossements prises avant leur disparition ont été récemment redécouvertes.
Une expédition américano-égyptienne dirigée par le paléontologue Peter Dodson s'est à nouveau rendue dans l'oasis de Baharija et semble avoir mis au jour du nouveau matériel de Spinosaurus qui n'a pas encore été décrit dans la littérature.
C'est en 1971 que l’Institut et Muséum de géologie et de paléontologie du Georg-August-Universität de Göttingen en Allemagne demande au docteur H. Alberti et deux de ses employés (O. Chérif et U. George) de récolter des ossements dans le « Continental Intercalaire » de la base de la Hammada du Guir près de la ville de Taouz au Maroc. Le matériel ramené à Göttingen comprend un maxillaire incomplet décrit plus tardivement par Buffetaut qui rapporte cet os du crâne au genre Spinosaurus.
Depuis cette mission paléontologique allemande, les autochtones, conscients de la richesse fossilifère de cette région et encouragés à développer un marché de fossiles, fouillent de toutes parts les niveaux fossilifères des sites multiples du plateau des Kem Kem et du bassin du Tafilalt situés dans le Sud-Ouest du Maroc. En 1975, un museau quasi complet fut découvert non loin de la ville de Taouz et entreposé dans les collections d'un particulier avant d'être acquis par le Musée d'Histoire naturelle de Milan en 2002 et décrit en 2005 comme étant celui d'un Spinosaurus aegyptiacus. Un museau incomplet ainsi qu'un dentaire gauche découverts dans les mêmes niveaux marocains et entreposés dans les collections du Natural History Museum de Londres furent également attribués à un Spinosaurus aegyptiacus de grande taille en 2003.
Un collectionneur de Cambridge (Brian Ebeharde) qui rassembla un grand nombre d'ossements provenant des Kem Kem légua une partie de sa collection au Canadian Museum of Nature, dont des vertèbres cervicales, un fragment d'os dentaire et des arcs neuraux de vertèbres dorsales qui furent rapportés à une nouvelle espèce de Spinosaurus, S. marroccanus.
Seule une expédition paléontologique menée par le paléontologue Paul Sereno fut lancée dans le Nord du vaste plateau des Kem Kem (non loin du poste frontière de Keneg ed Dal) en 1996. Un ossement érodé, initialement non-identifié, fut entreposé dans les collections paléontologiques de l'Université de Chicago jusqu'en 2002 avant d'être décrit et identifié par plusieurs scientifiques comme étant le nasal d'un Spinosaurus aegyptiacus en 2005.
Au printemps 1985, une collaboration entre le « Programme de cartographie géologique et inventaire des substances utiles dans le Sud tunisien » et le laboratoire de Paléontologie des Vertébrés de l'Université de Paris VI permet de découvrir un nouveau gisement de vertébrés non loin de la localité de Bir Miteur, située à une vingtaine de kilomètres au nord-ouest de Foum Tatahouine. Ce gisement a livré une faune assez riche de poissons et de reptiles, dont des dents attribuées au genre Spinosaurus sp. par Bouaziz et ses collègues en 1988 et en 2000.
Mohamed Ouaja de l'Office National des Mines de Tunisie découvre également non loin de la ville de Ghoumrassen dans la région de Tataouine (sud-est de la Tunisie) un fragment de mâchoire inférieure (dentaire) rapporté à l'espèce Spinosaurus aegyptiacus.
En 1998, des ossements provenant du site de Gara Samani, localisé au nord-ouest du Tademaït en Algérie et comprenant un museau incomplet, des fragments dentaires, des centres de vertèbres cervicales et l'arc neural d'une vertèbre dorsale sont rapportés à l'espèce Spinosaurus maroccanus.
Plus récemment, Brusatte et Sereno ont mentionné l'existence de dents provisoirement référées au genre Spinosaurus sp. dans la région d'Iguidi (désert du Ténéré), au Niger. Des dents attribuées également à Spinosaurus sp. semblent avoir été découvertes au Cameroun (province du Nord), au Kenya (province de la Vallée du Rift) ainsi qu'en Libye (région du djebel Nefoussa). Cependant, aucune publication détaillée sur ces dents n'a encore vu le jour, si bien que leur attribution au genre Spinosaurus reste pour le moment hypothétique.