После поражения в Крымской войне 1853-1856 годов Новороссийск (в то время Новороссийское укрепление) был разрушен, и в связи с этим Высочайшим приказом от 31 марта 1860 года, упразднен. К этому времени на его месте было построено Константиновское укрепление. В центре этого укрепления находилась Церковная площадь, которая была окружена различными строениями, и по периметру укрепление было огорожено каменной стеной (парк имени Ленина).

27 сентября 1866 года в торжественной обстановке состоялось повторное открытие города Новороссийска. А в 1868 году по распоряжению инженерного управления Кавказского военного округа начали разбор крепостной стены Константиновского укрепления, в виду успешного выполнения возложенных на него функций, и в 1869-м полностью завершили работы.

Параллельно с этими событиями началась активная застройка Новороссийска. В 1869 году напротив Церковной площади купец Савва Матвеевич Обрадович строит каменный двухэтажный дом, высотой 5,6 метров и площадью 457,7 квадратных метров, облицованный с фасадных сторон кирпичом. Сам Савва Матвеевич Обрадович, серб по происхождению, широко занимался торговой деятельностью – продавал муку, аптекарские и лесные товары. Участок под это здание, находившийся в 22 квартале на углу улиц Вельяминовской и Николаевской, он выкупил у жены Новороссийского купца I гильдии Елизаветы Ивановны Кирьяковой.

На момент постройки дом Обрадовича был одним из первых и лучших гражданских строений Новороссийска и сразу стал его достопримечательностью. Изображение здания неоднократно украшало почтовые открытки конца XIX – начала XX веков.

С 1891 по до 1918 годы второй этаж дома арендовало Новороссийское отделение Азовско-Донского Коммерческого банка, который был четвертым по размерам операций и третьим по значению в России. Новороссийское отделение Азовско-Донского Коммерческого банка участвовало в финансировании цемзаводов "Цепь" и "Черноморского цементного производства", а также вело учет векселей местных купцов, выдавало ссуды. Нижний этаж также сдавался внаем.

В 1894 году на первом этаже здания со стороны Николаевской улицы размещалось Агентство Донского соединенного пароходного общества и Варшавского страхового от огня общества. В 1899-м в доме Обрадовича ненадолго останавливался консул Италии. Также в разное время здесь жили и принимали больных врач А.М. Попов (конец 1890-х гг) и стоматолог Г.Л. Александрович (1903-1912 гг.).

В 1920-е годы здание занимало Управление милиции I района.

О том, под какие цели использовался "Дом доходный торговца мукой Саввы Матвеевича Обрадовича" в годы Великой Отечественной войны, доподлинно неизвестно.

С 1991 года по настоящее время в здании располагается телерадиокомпания "Новая Россия", чьими усилиями за счет частных средств оно было полностью отреставрировано и приведено в первозданный вид в соответствии с найденными в городском архиве фотографиями.