Il palazzo detto del "Fontego dei Turchi", sede del Museo, fu eretto nella prima metà del XIII secolo dalla famiglia Pesaro. Nel 1381 venne donato a Nicolò d'Este, marchese di Ferrara, e dopo numerosi passaggi di proprietà fu assegnato ai Turchi, cui rimase in uso (come sede commerciale) sino al 1838. Il palazzo venne integralmente restaurato a partire dal 1865, divenendo sede prima del Museo Correr, poi del Museo di Storia Naturale.

Nel 2010 il Museo ha riaperto al pubblico con una sede rinnovata e accogliente per l'educazione scientifica e naturalistica delle nuove generazioni. È un allestimento nuovo e suggestivo, lungo undici sale al primo piano del Fondaco dei Turchi. Nuove aree di accoglienza al piano terra, con un giardino recuperato per il museo e per la città. Un approccio museologico e un impianto museografico moderni e originali e altri programmi di ampliamento. Dopo i lavori di restauro globale che hanno interessato l'edificio negli ultimi anni, consentendone il risanamento e l'adeguamento impiantistico, e dopo il completamento del restauro delle collezioni, si è conclusa una fase importante del nuovo riallestimento. Riapre al pubblico, in uno dei palazzi più noti della città, un museo radicalmente rinnovato, che da un lato recupera e riqualifica la tradizione scientifica e didattica, dall'altro sperimenta e propone, sul piano dei contenuti e dell'allestimento, strumenti e metodi nuovi, frutto del lavoro di un gruppo affiatato che comprende, a fianco dei responsabili scientifici del museo, architetti e professionisti della comunicazione.
Per il riallestimento sono state concepite e sviluppate - grazie alla vastità e all'ampiezza delle collezioni - tre diverse aree tematiche: paleontologia, collezionismo naturalistico, forma e funzione negli esseri viventi.
Nel 2011 è stata inoltre inaugurata la Galleria dei Cetacei.