Севастопольську картинну галерею було відкрито 6 листопада 1927 р. Створено її на основі Ялтинського народно-художнього музею (відкритого у грудні 1920 р.). на базі націоналізованих приватних колекцій, палацових зібрань Лівадійського палацу, зібрань князя Голіцина в Новому Світі, князів Барятинських в Уч-Чамс тощо), колекцій картин російської школи з фондів Державної Третьяковської галереї, Центрального музею Тавриди та розформованого в 1926 р. Румянцевського музею. У 1941 р. колекції галереї було вивезено на Кавказ, потім у м. Томськ її директором М. П. Крошицьким. З 1945 по жовтень 1956 р. вони експонувалися в приміщенні Сімферопольської картинної галереї, а в листопаді 1956 р. повернулися до Севастополя. Будівля, в якій перебуває галерея з 1958 р., вражає величезною кількістю декору, деталями різних епох і стилів (зведена 1899 р.). Це одна з небагатьох будівель, що збереглися в місті в роки війни.
У 1965 р. галерея отримала назву Севастопольського художнього музею. Його зібрання — одне з найкращих в Україні: у ньому зберігається понад 4 тис. творів образотворчого мистецтва.
У залах розгорнуто експозицію трьох відділів: західноєвропейського, російського та українського дореволюційного і радянського мистецтва. Колекція західноєвропейського мистецтва представлена творами художників XVI-XIX ст. Італії, Голландії, Фландрії, Франції та Німеччини. Виділяються картини «Мадонна з немовлям» невідомого художника флорентійської школи початку XVI ст., «Селянський сніданок» невідомого венеціанця кола Я. Бассано, «Святе сімейство» неаполітанця Л. Джордано; французів К. Лефевра, Г. Робера, А. Ранка та ін. Широко представлений у колекції голландський і фламандський натюрморт, «малі голландці».
У відділі російського та українського дореволюційного мистецтва — твори В. Тропініна, М. Воробйова, С. Галактіонова, І. Хрупкого, Т. Неффа, В. Орловського.
В експозиції, присвяченій мистецтву другої половини XIX ст., демонструється творчість художників-передвижників: В. Маковського, І. Крамського, І. Левітана, І. Шишкіна, В. Поленова. Гордістю зібрання є картина М. Касаткіна «У коридорі окружного суду» (1900 р. експонувалася на Всесвітній виставці в Парижі, удостоєна срібної медалі). Тут же твори видатних майстрів І. Рєпіна, І. Айвазовського, В. Верещагіна, В. Сєрова, М. Нестерова, А. Бенуа, О. Васнецова, А. Архипова, К. Коровіна.
Експозиція радянського відділу починається з творів художників старшого покоління — М. Терпсіхорова, К. Юона, В. Бакшеєва, С. Малютіна, В. Бялиницького-Бірулі, М. Самокиша, К. Богаєвського та ін. 
У музеї є роботи Е. Штейнберга, О. Купріна, М. Волошина, К. Петрова-Водкіна, П. Кончаловського, О. Дейнеки.
За останні роки колекція музею поповнилася творами кримських і почасти севастопольських художників: заслужених художників УРСР Г. Брусенцова і В. Коваленка; 3. Філіппова, Е. Ареф’єва, П. Мірошниченка, М. Афанасьєва, В. Бернадського, О. Сухоруких, М. Василенка, П. Коломійцева, Л. Мельникова, М. Чухланцева, А. Шорохова.
У залах музею експонуються роботи майстрів скульптури — С. Коненкова, І. Гінзбурга; кримських скульпторів Л. Смерчинського, Р. Сердюка, С. Чижа, А. Білостоцького, В. Гордєєва та ін.
Колекція графіки налічує понад 2 тис. аркушів. Серед них: І. Айвазовський, І. Рєпін, А. Беггров, О. Орловський, М. Врубель, М. Волошин, І. Крамской, В. Фаворський.
Колектив музею широко пропагує художню спадщину минулого і творчість радянських художників. Колекції експонувалися на багатьох виставках (у т. ч. міжнародних).
Щорічно музей відвідують близько 75 тис. осіб. Проводяться екскурсії, музичні вечори, присвячені знаменним датам у житті художників, за участю акторів, музикознавців.