В 1776 году появилось село Федоровка. В 1832 году село переименовано в Новую Одессу, так как в нём находился штаб Одесского уланского полка. В 1860 году Новая Одесса стала местечком. В 1923 году Новая Одесса стала райцентром. В 1965 году Новой Одессе присвоен статус поселка городского типа, а в 1976 году - города районного подчинения. В результате реформы 2020 года город Новая Одесса присоединен к Николаевскому району, является центром Новоодесской городской общины.
Герб Новой Одессы разработан авторской группой М. Штомпель, Р. Кочкуров, И.Янушкевич и утвержден решением горсовета № 7 от 29 апреля 2005 года. Cогласно "Положению о содержании, описании и порядке использования герба и флага г.Новой Одессы":
Герб - это прямоугольный с закруглением щит. В голубом поле золотая (жёлтая) казачья пика с серебряным наконечником. Над пикой стилизованный малиновый крест с золотой (жёлтой) окантовкой и лучами. Внизу серебряный якорь-кошка, который обвит канатом и создает орнамент.
Малиновый крест символизирует первые поселения - зимовники казаков Бугогардовской паланки, основанные на месте нынешнего города.
Пика симаолизирует размещение на территории современной Новой Одессы Харьковского пикинерного полка, сформированного из Запорожских казаков, которые основали слободу Федоровку, переименованную в дальнейшем в Новую Одессу.
Якорь означает грузовую пристань, построенную на берегу Южного Буга в конце XIX века, что ускорило развитие торговли и промышленности в Новой Одессе. Якорь в геральдике - древний символ надежды.
Голубой цвет герба символизирует величие, красоту города и Южного Буга.
Малиновый цвет - символ казачества, означает мужество и храбрость.
Серебряный цвет - символ величия и красоты.
Герб увенчан серебряной короной в виде каменной башни и означает для Новой Одессы статус города.
Герб имеет картуш в национальном украинском стиле и обрамление в виде сплетенных зеленого лаврового венка с золотым пшеничным колосом.
Внизу венка на красной ленте надпись - Новая Одесса и год основания Новой Одессы".
Использовано изображение герба на официальном сайте городского Совета Новой Одессы