Поблизу Нової Одеси і Криворіжжя виявлено залишки мезолітичної стоянки і поселень доби бронзи та перших століть нашої ери. Біля селища розкопано також кургани скитських часів, на одному з яких знайдено кам’яну бабу кочівників XI—XIII століть.
Завжди з версією, ще до 1739 року тут уже існувало село, яке називалося Олексіївське. Тут селилися старовіри, які втікали від утисків у Російську імперію. Фельдмаршал Мініх залишив опис села, під час свого походу на Османську імперію у 1737 році. військові зупинилися табором на місці сучасного села Троїцьке (навпроти села Андріївка, створеного на картах і планах Мініха), а на місці сучасної Нової Одеси на російській карті Мініха було позначено досить велике село старовірів, у якому вже виснувало дві церкви.
У 1976 році отримав статус міста.
У 2010 році розпочато будівництво зерноперевантажувального терміналу компанії «НІБУЛОН», у 2011 році відкрито філію. Саме відкриття філії компанії в місті та пізніше ще перше вище за технікою Південного Бугу стало початком відродження занепалого судноплавства Південного Бугу. Відтоді біля причалів Нової Одеси зараз можна зустріти лише рибацькі човни, але й сучасні буксири та несамохідні судна вантажопідйомністю до 4000 тон збіжжя. Також з 2017 по 2019 роки в період навігації діяв пасажирський річковий маршрут Вознесенськ — Ковалівка — Нова Одеса — Миколаїв, який через нерентабельність згодом ліквідували.
Починаючи з 2010 року, за останнє десятиліття, у Новій Одесі почали будуватися великі компанії: супермаркет АТБ; велика олійна “Сан Флавер” та розбудовуються менші олійні, яких у місті тепер ще кілька; великий будмаркет Люкс, при якому об’єкти компенсуються навколишня територія та будуються дрібніші об’єкти торгівлі й обслуговування населення. На місці колишніх корівників та свиноферми ТОВ імені Т.Г. Шевченка (колишній колгосп імені Т.Г. Шевченка) починають діяти ферма з вирощування біків та вівцеферма. У 2020 році знесено резервуари давно недіючої нафтобази і на її місці розбудовується автомобільне підприємство.
У 2018 році міська рада під тиском громадськості виділяє ділянку землі під майбутній парк загиблих Захисникам України. Силами ветеранів війни на цій ділянці встановлюється тимчасовий пам’ятний знак та майви́льно (флагшток) під державний прапор. 14 жовтня, в день Захисника України, парк та тимчасовий пам’ятний знак урочисто відкрили та провели змагання серед школярів імені одного із загиблих учасників АТО Котєшевського Дмитра Івановича. До кінця року серед навчальних закладів було проведено конкурс на назву парку і таким чином визначили, що парк матиме назву «Парк Нескорених». Декілька років все так і залишилося, у «Парку Нескорених» проводяться заходи, присвячені віковічненню пам’яті загиблих Захисників, розміщені квіти, сили ветеранів, учнів шкіл та гімназій, небайдужих громадян у парку висаджуються квіти та кущі, але розвиток парку не відбулося. Лише у 2021 році ситуація зрушила з місця, місцева влада активізувалась щодо проектування та розбудови парку. 23 квітня 2021 року ветерани, спільнота “Бузькі силовики” з міською владою висадили 9 дерев у пам’ять про 9 загиблих на сході України бійців з території колишнього Новоодеського району. До кінця року проведено ще кілька висадок квітів та дерев, міською владою було затверджено план парку.
25 жовтня 2020 року – створена Новоодеська міська територіальна громада. З 1 грудня 2020 року Новоодеський район ліквідовано, Нова Одеса відтепер є центром міської територіальної громади. Територія колишнього Новоодеського району тепер входить до складу Миколаївського району.
