Зграда у којој је смештена Галерија природњачког музеја једна је од најстаријих зграда у комплексу Београдске тврђаве. Претпоставља се да је подигнута крајем 18. века, а уцртана је на једном турском плану из четрдесетих година 19. века. Сматра се да је ова зграда, која представља прелаз од балканско-турског ка европском градитељству, направљена за потребе страже која је чувала главни прилаз Стамбол капији. 

У сталној поставци посебно привлаче пажњу остаци животињског света леденог доба и фосилне врсте које указују да је на простору Београда пре петнаест милиона година постојало топло Панонско море.