Севастопольский художній музей заснований на базі художнього музею Ялти, створеного з приватних колекцій Південного берега Криму і літньої імператорської резиденції в Лівадійському палаці, націоналізованих у 1920 році. В 1927 році частина ялтинської колекції була передана Севастополю і доповнена творами живопису з державного музейного фонду, центральних музеїв Москви і Петербургу. Картинна галерея була відкрита 6 листопада 1927 року. У 1931 році почав комплектуватися відділ радянського періоду, був створений кабінет гравюри. У 1941 році севастопольські зібрання налічували дві з половиною тисячі творів живопису, графіки, скульптури, декоративно-прикладного мистецтва.
В період Великої Вітчизняної війни основна частина художніх цінностей була вивезена і героїчно збережена директором Севастопольської картинної галереї М.П.Крошицьким. Після війни твори мистецтва Севастопольської картинної галереї тимчасово експонувалися в Сімферополі: Севастополь був повністю зруйнований, будівля музею згоріла. 5 листопада 1956 року галерея знов відкрилася в рідному місті, а з 1965 року називається — Севастопольський художній музей. У 1991 році музею було присвоєно ім'я Михайла Павловича Крошицького. В даний час у музеї понад 8000 творів живопису, графіки, скульптури і декоративно-прикладного мистецтва.