Įsikūręs Nikolajevo aikštėje. N. Leontovič.

Remiantis darbo rezultatais, zoologijos sodas buvo pirmasis tarp Ukrainos zoologijos sodų 1993 m., buvo priimtas į Europos zoologijos sodų ir akvariumų asociaciją (EAZA). Zoologijos sodas dalyvauja 18 Europos retų rūšių veisimo programų (EEP), yra Europos ir Azijos regioninės zoologijos sodų ir akvariumų asociacijos (EARAZA) ir Tarptautinės gyvūnų registro sistemos (ISIS) narys. 2003 m. gegužės mėn. Mykolaivo zoologijos sodas buvo pirmasis zoologijos sodas Ukrainoje, priimtas į Pasaulinę zoologijos sodų ir akvariumų asociaciją (WAZA).
1901 m. balandžio 26 d. Meras Nikolajus Pavlovičius Leontovičius įkūrė savo privačią kolekciją, kuri buvo jo namuose. Leontovičiaus kolekcija buvo plačiai žinoma Rusijoje ir Europoje. Akvariume buvo elektriniai kompresoriai ir šildytuvai. Žuvys buvo laikomos 75 akvariumuose. Kolekcijoje buvo apie 50 žuvų ir varliagyvių rūšių, virš 1000 egzempliorių. Nikolajus Leontovičius nuolat skelbė straipsnius apie akvariizmą, buvo aktyvus Nikolajevo gamtos mylėtojų draugijos narys. 1918 metais Leontovičiaus kolekcija buvo nacionalizuota, o jis pats paskirtas pirmuoju Valstybinio akvariumo direktoriumi.

Patyręs didelių nuostolių, akvariumas išgyveno pilietinį karą. 1922 m. birželio 25 d. įvyko antrasis iškilmingas Nikolajevo valstybinio akvariumo atidarymas. Šiemet joje apsilankė apie 40 tūkst. Apsilankymas buvo nemokamas. Iki 1923 metų Nikolajevo valstybinį akvariumą išlaikė vietos visuomenės švietimas, vėliau jis perėjo į valstybės biudžetą, o nuo 1934 m. kovo – į miesto biudžetą.
1925 m. akvariume buvo atidarytas zoologijos skyrius, kuris tapo žinomas kaip akvariumas-zoologijos sodas. Iš Askanija-Novos buvo atvežti stumbrai, kupranugariai, jakai, elniai, muflonai, stručiai. Specialiai zoologijos sodui buvo nupirkti lokiai, vilkai, lapės, beždžionės. Teritorija padidinta iki 0,75 ha. Buvo pastatyti aptvarai kanopiniams gyvūnams, plėšrūnų narvai, įrengtas parkas. 1928 m. zoologijos sodo darbuotojai buvo 9 žmonės. Parke gyveno Nikolajus Leontovičius, jo šeima ir kai kurie darbuotojai.

1934 metais prasidėjo nepagrįstos Leontovičiaus ir jo šeimos represijos. 1937 m. liepos 28 d. buvo suimtas, apkaltintas ryšiais su kontrrevoliucine inteligentija ir dalyvavimu karininkų organizacijoje. 1935 metų gruodžio 4 dieną į akvariumą-zoologijos sodą mokslininku atvyko Fiodoras Grigorjevičius Ničikovas, baigęs Odesos profesinio mokymo institutą ir aspirantūrą Odesos valstybiniame mokslo ir biologijos institute. Į zoologijos sodą atvykus Fiodorui Ničikovui, darbas buvo pastatytas ant mokslinio pagrindo: pradėtos vesti paskaitos, ekskursijos, konsultacijos.
1941 m. rugpjūčio 16 d. nacių kariuomenė įžengė į miestą. Zoologijos sodas nebuvo evakuotas. Okupacijos metais zoologijos sodas buvo atviras lankytojams. 1942 metų rugsėjį zoologijos sode dirbo 24 žmonės. Zoologijos sodo muziejuje saugomi autentiški to meto įėjimo bilietai, atspausdinti ukrainiečių ir vokiečių kalbomis.

Nuo 1948 m. akvariumas-zoologijos sodas buvo pervadintas į Nikolajevo zoologijos sodą. Tuo metu jis buvo pavaldus rajono vykdomajam komitetui, Kultūrinio švietimo skyriui ir finansuojamas iš rajono biudžeto. 1950-aisiais zoologijos sodo kolekcija buvo labai išplėsta. Jame pasirodė pumos, sniego leopardas, baltieji lokiai, dėmėtoji hiena, Himalajų lokys. 1955 metais buvo atvežta Indijos dramblys Marija, kurią Nikitai Chruščiovui padovanojo Indijos ministras pirmininkas Jawaharlal Nehru.

1970 metais naujoje teritorijoje pradėtos statybos. Pinigų, kaip įprasta, neužteko, statybos vyko itin vangiai. Kai kurie miesto vadovai manė, kad būtų lengviau uždaryti zoologijos sodą. Tačiau nuo 1974 m. zoologijos sodas pradėtas statyti liaudies statybos būdu.
2001 metų rugsėjo 7–10 dienomis zoologijos sode vyko tarptautinė mokslinė ir praktinė konferencija. Zoologijos sodo šūkis „Tik bendromis pastangomis išgelbėsime laukinių gyvūnų pasaulį“ tapo jo pavadinimu ir pagrindine tema. Konferencijoje dalyvavo daugiau nei 60 žmonių iš 29 zoologijos sodų 10 šalių. 2001 m. rugsėjo 9 d. įvyko iškilmingas naujos aikštės ir paminklo zoologijos sodo įkūrėjui Nikolajui Pavlovičiui Leontovičiui atidarymas. Paminklo autoriai – Inna, Jurijus ir Viktoras Makušinai.

Nuo 1988 m. zoologijos sode veikia istorijos muziejus. Medžiaga kūrybai pradėta rinkti devintojo dešimtmečio pradžioje. Muziejuje eksponuojami dokumentai, nuotraukos, Nikolajaus Leontovičiaus, Fiodoro Ničikovo asmeniniai daiktai, darbuotojų atsiminimai, kaukolių ir gyvūnų iškamšų kolekcija, kadaise gyvenusi zoologijos sode, kiaušinių kolekcija, kitų zoologijos sodų žemėlapiai ir vadovai.
2003 m. Ukrainoje vyko 100 geriausių prekių ir paslaugų konkursas dėl produktų kokybės. Konkursą globojo Ukrainos prezidentas Leonidas Kučma ir Ministrų kabinetas. Pagal nacionalinio etapo rezultatus Nikolajevo zoologijos sodas buvo pripažintas nugalėtoju nominacijoje „Paslauga“, apdovanotas valstybiniu kokybės ženklu. Apdovanojimų ceremonija įvyko 2004 m. kovo 15 d. Nacionaliniuose rūmuose „Ukraina“ Kijeve.