Historie paleontologické sbírky sahá až k počátkům Národního muzea. Vždyť duchovním otcem muzea byl paleontolog Kašpar Maria hrabě Sternberg, který do vínku právě založené instituce věnoval všechny své sbírky i vědeckou knihovnu. Sbírková i vědecká aktivita se v muzeu velmi zintenzivnila v polovině 19. století za Antonína Friče, který je považován za zakladatele geologicko-paleontologického oddělení muzea. Stal se jeho ředitelem v roce 1864. Pod jeho vedením bylo pro sbírky získáno a publikováno velké množství paleontologického materiálu z českého paleozoika a křídy. Křídovou flóru zpracovali Josef Velenovský a později Edvín Bayer. K opravdu zásadnímu daru došlo v roce 1884, kdy byla otevřena závěť francouzského paleontologa Joachima Barranda. Tento francouzský učenec pobývající v Čechách přes půl století odkázal muzeu sbírku čítající přes 300 tisíc sbírkových předmětů, rozsáhlou knihovnu, terénní dokumentaci a 10 000 zlatých na dokončení jeho rozsáhlého díla „Systeme silurien du centre de la Boheme“.

Nejvýraznější osobností meziválečného období rozvoje oddělení byl paleobotanik František Němejc. Do muzea nastoupil v roce 1924 a svojí intenzivní sběratelskou a vědeckou činností výrazným způsobem zasáhl do všech dějů v oddělení. Obohatil výrazně paleobotanickou sbírku, kde se soustředil především na kvartérní a karbonskou flóru. Muzejní zoopaleontologická kolekce byla postupně doplňována o systematické sběry Jana Kolihy, Bedřicha Boučka a Ferdinanda Prantla, kteří publikovali materiál z českých i moravských prvohor a popsali i velké množství nových taxonů.

Do chodu geologicko-paleontologické oddělení zasáhla výrazně druhá světová válka. Vzhledem k nebezpečí, které hrozilo, byla nejcennější část sbírek přesunuta na zámek v Kopidlně, ostatní materiál včetně knihovny byl svezen do suterénních skladů. Toto prozíravé opatření uchránilo velké množství sbírek a především knihovnu oddělení od zkázy způsobené zásahem německou leteckou bombou 8. května 1945.

V poválečném období se oddělení z počátku pod vedením Františka Němejce po té Vlastimila Zázvorky utěšeně rozrůstalo. Rozrůstaly se i sbírky oddělení na základě sběrů Františka Němejce, Ferdinanda Prantla a Vlastislava Zázvorky, ale také zaměstnanců jiných vědeckých institucí. Patří k nim např. Vladimír Havlíček, Milan Šnajdr, Jiří Kříž, Rudolf Prokop, Alois Přibyl, J. Vaněk.
V roce 1964 v rámci reorganizační změny vzniklo Přírodovědecké muzeum. V rámci stejné změny bylo geologicko-paleontologické oddělení změněno na paleontologické. Bylo to po 100 letech od prvního použití toho jména na základě Fričova požadavku k Správnímu výboru Společnosti Muzea království českého.

Od 60. let byl do muzea pravidelně ukládán nový typový materiál k fytopaleontologickým pracím Františka Holého, Zlatka Kvačka, Čestmíra Bůžka a Ervína Knoblocha. Podobně tomu bylo v paleozoologii. Zde je nutné připomenout celoživotní dílo Radvana Horného, Rudolfa Prokopa, sbírku Ladislava Marka, sbírku křídových bezobratlých Olgy Nekvasilové a Jiřího Žítta. Velmi významnou kolekci fosilních obratlovců, především žab, se podařilo získat od Zdeňka V. Špinara. Podobně byla získána sbírka prvohorních fosilií od Ivo Chlupáče a sbírka obratlovců od Oldřicha Fejfara. Z důležitých akcesí posledních let je nutné zmínit získání velké a nesmírně důležité kolekce třetihorních obratlovců a rostlin ze severních Čech od Severočeských dolů a.s., Zdeňka Dvořáka, Pavla Coufala a Oldřich Janečka. Velké a důležité sbírky prvohorních bezobratlých byly v poslední době zakoupeny od Vratislava Korduleho a Vladislava Kozáka.