Здание, в котором расположен Одесский художественный музей было построено в период между 1824 и 1828 годами. Автор проекта не установлен. По окончании строительства сооружение было освидетельствовано известным одесским архитектором Ф. К. Боффо. Первой владелицей дворца была графиня Ольга Станиславовна Нарышкина (урожденная Потоцкая).
В 1888 году дворец был приобретен Одесским городским головой Г. Г. Маразли — видным общественным деятелем, коллекционером и меценатом. В 1892 году Г. Г. Маразли передает дворец городу, с целью устройства в нём музея изящных искусств. Открытие музея состоялось 24 октября (6 ноября) 1899 года.
Архитектура дворца воплощает в себе лучшие традиции русского классицизма начала XIX века. Центрическая композиция постройки, состоящая из двухэтажного корпуса с портиком из шести колонн коринфского ордера, поддерживающих фронтон, двух симметрично расположенных одноэтажных флигелей, соединённых округлыми галереями, отличается строгим и гармоничным изяществом.
Дань эпохи романтизма — обустроенный под центральной частью основного корпуса — обширный грот со сводчатым перекрытием имитирующий природную пещеру и искусственным водопадом. От него в сторону идут подземные галереи имевшие выход в обширный сад, спускавшийся по склону к морскому берегу. В небольшой экспозиции перед спуском в грот можно ознакомиться с историей дворца и создания в нём музея. Со стороны моря под основным зданием, в цокольном помещении находится обширная галерея. На сводчатых перекрытиях и стенах, которой сохранились настенные росписи, выполненные вовремя проведения во дворце и прилегающем к нему саду «Выставки Домоустройства», проходившей в 1895 году. В настоящее время в этой части дворца располагается экспериментальная галерея «Желтые Великаны».