Будівлю, в якій розташовано Одеський художній музей, було збудовано в період між 1824 і 1828 роками. Автор проекту невідомий. Після закінчення будівництва споруду освідчив відомий одеський архітектор Франс Карлович Боффо. Першою власницею палацу була графиня Ольга Станіславівна Наришкіна (уроджена Потоцька).

У 1888 році палац придбав одеський міський голова Григорій Григорович Маразлі — відомий громадський діяч, колекціонер і меценат. У 1892 році він передав палац місту з метою створення в ньому музею витончених мистецтв. Відкриття музею відбулося 24 жовтня (6 листопада) 1899 року.

Архітектура палацу втілює в собі кращі традиції руського класицизму початку ХІХ століття. Центрична композиція споруди вирізняється строгою та гармонійною витонченістю — двоповерховий корпус з портиком із шести колон корінфського ордеру, що підтримують фронтон, і два симетрично розташовані одноповерхові фліґелі, з’єднані округлими галереями.

Данина епосі романтизму — облаштований під центральною частиною основного корпусу грот зі склепінчастим перекриттям, що імітує природню печеру зі штучним водоспадом. Від нього в бік ідуть підземні галереї, що мали вихід до просторого саду, який спускався схилом до морського узбережжя. У невеликій експозиції перед спуском до гроту можна ознайомитися з історією палацу та створення в ньому музею.

З боку моря під основною будівлею у цокольному приміщенні знаходиться простора галерея. На склепінчастих перекриттях та стінах збереглися настінні розписи, виконані під час проведення у палаці та прилеглому саду «Виставки домоустройства» у 1895 году. Нині в цій частині палацу розташовано експериментальну галерею «Жовті велетні».