Сахалинский областной художественный музей был основан в 1983 году. В феврале 1987 года молодой музей открыл свою первую экспозицию. Она занимала площадь почти в 100 квадратных метров и представляла около трех десятков картин.
В 1988 году музей въехал в новое помещение по адресу улица Ленина, дом 137. В 1999 году здание музея было объявлено памятником истории и культуры регионального значения.
К началу 2000-х годов музей накопил небольшую, но ценную коллекцию русского искусства XIX — начала XX века. Она собиралась более десяти лет, в ее основу легли работы, приобретенные первым директором музея Раисой Самойловной Гороховой в Ленинграде и Москве в конце 1980-х годов. Графические работы 20 русских художников были переданы в СОХМ из Государственного Русского музея. Художником-экспозиционером «русского» зала стала Наталья Андреевна Бржезовская.