Le prime collezioni ospitate nel museo furono vendute dal medico irlandese sir Hans Sloane (1660–1753) al governo britannico, ad un prezzo di realizzo che era di molto inferiore alle quotazioni di mercato dell'epoca e venne finanziato tramite una lotteria. La collezione di Sloane, che comprendeva piante essiccate e scheletri di animali e umani, fu esposta per la prima volta nel 1756 a Montagu House, nei pressi di Bloomsbury, futura sede del British Museum.

Gran parte della collezione Sloane scomparve nei primi decenni del diciannovesimo secolo. George Shaw (custode del museo dal 1806 al 1813) vendette molti esemplari al Royal College of Surgeons e fece periodicamente cremazioni di materiale nel parco del museo. I suoi successori hanno anche chiesto ai fiduciari l'autorizzazione a distruggere esemplari decomposti. Il rapporto annuale del 1833 afferma che non rimaneva nessuno dei 5 500 insetti elencati nel catalogo di Sloane. Il Museo di Storia Naturale ebbe un danno di immagine che indusse il Tesoro a revocargli l'autorizzazione a custodire gli esemplari raccolti a spese del governo.[1][2]

J. E. Grey, custode della sezione zoologica dal 1840 al 1874, lamentava in quegli anni l'incidenza delle malattie mentali fra il personale: George Shaw ad esempio paventò di mettere mano su qualsiasi esemplare che non fosse catalogato nella dodicesima edizione del Systema Naturae di Linneo; un altro dipendente aveva invece rimosso tutte le etichette e i numeri di registrazione dai reperti entomologici, classificati da un collega. L'enorme collezione di conchiglie curata da Hugh Cuming fu acquisita dal museo e la stessa moglie di Gray trasportò i vassoi aperti lungo il cortile nel corso di una tempesta, che spazzò via tutti i dati di catalogazione, danneggiando in modo irreparabile i reperti.[3][senza fonte]

Nel 1835, davanti ad una commissione parlamentare d'inchiesta, sir Henry Ellis affermò che il bibliotecario principale, Antonio Panizzi, e i suoi colleghi più esperti stavano portando avanti da anni una politica che non valorizzava in alcun modo il patrimonio scientifico e di storia naturale dell'istituzione. Per tali motivi, il paleontologo inglese Richard Owen fu nominato nel 1856 quale sovrintendente preposto a tali aree tematiche della collezione museale. Bill Bryson commentò i cambiamenti introdotti con le seguenti parole: "rendendo il Museo di Storia Naturale un'istituzione per tutti, Owen ha trasformato le nostre aspettative riguardo allo scopo e al'utilità dei musei".[4]

Convinto che fossero necessari spazi più ampi per ospitare le sezioni di storia naturale, Owen acquistò degli appezzamenti di terreno a South Kensington e nel 1864 bandì un concorso internazionale, vinto dal progetto di Francis Fowke (1823-1865), capitano dell'esercito. ingegnere civile e architetto. Alfred Waterhouse aggiunse due facciate in stile neoromanico, ispirate alle sue frequenti visite nel Continente.[5] I progetti originali prevedevano la costruzione di due ali laterali dell'edificio principale, ma furono accantonati per motivi di bilancio; al loro posto, furono in seguito edificate le Gallerie della Terra e dal Centro Darwin.

I lavori iniziarono nel 1873 e furono completati nel 1880. Il nuovo museo fu inaugurato nel 1881, anche se il trasferimento dal vecchio museo non fu completato fino al 1883.

Sia gli interni, sia gli esterni dell'edificio di Waterhouse fanno ampio uso di piastrelle in terracotta, prodotte dalla società con sede a Tamworth di Gibbs e Canning Limited, in grado di resistere all'inquinamento atmosferico della Londra vittoriana. Le piastrelle e i mattoni presentano molte sculture con motivi a rilievo di flora e fauna, relativi a specie viventi ed estinte custodite rispettivamente nelle ali ovest e est dell'edificio. Questa esplicita separazione delle due categorie, richiesta da Owen, fu vista all'epoca come un rigetto della teoria darwiniana della selezione naturale.[6]

L'asse centrale del museo è allineato con la torre dell'Imperial College di Londra (ex Istituto Imperiale), la Royal Albert Hall e l'Albert Memorial più a nord. Questi fanno tutti parte del complesso noto colloquialmente come "Albertopolis".

Dopo l'apertura, il Museo di storia naturale rimase dal punto di vista legale una sede distaccata del British Museum, il cui nome ufficiale era British Museum (Natural History), abbreviato nella letteratura scientifica come BM (NH). Nel 1866 fu presentata una petizione al Cancelliere dello Scacchiere, firmata dai capi delle società reali, linnee e zoologiche, nonché da naturalisti come Darwin, Wallace e Huxley, per chiedere la concessione dell'autonomia al Museo di Storia Naturale dal British Museum. La petizione aprì un acceso dibattito durato più di un secolo. Con l'approvazione del British Museum Act del 1963, il British Museum (Natural History) divenne un'istituzione indipendente con un proprio consiglio di fondazione, ma con il vecchio nome, per il quale alla Camera dei Lord era stata proposta la modifica. Solamente nel 1989 il museo ebbe facoltà di cambiare la propria denominazione in Natural History Museum, cessando di dover utilizzare il nome di British Museum (Natural history) nella pubblicità e nelle pubblicazioni per i visitatori. Infine, il Museums and Galleries Act del 1992 mutò ufficialmente il nome in Natural History Museum.