Свою историю музей ведёт от 1921 года, когда на основе собрания художественных произведений, хранившихся с конца XIX века в Городском музее (ныне Красноярский краеведческий музей) был создан отдел искусства и художественной старины имени В. И. Сурикова.
Многие экспонаты тогда были получены из частных собраний. Дарителями музея становились представители известных красноярских фамилий – Матвеевы, Суриковы, Юдины, Гадаловы. Значительную часть художественной коллекции краеведческого музея составляли произведения, собранные красноярским золотопромышленником, любителем и ценителем искусств П. И. Кузнецовым, помогавшим материально В. И. Сурикову в годы учёбы в Академии художеств.
В 1958 году на базе Красноярского краеведческого музея в отдельном здании была открыта Красноярская художественная картинная галерея. Она занимала в то время нижний этаж жилого дома No 68 по проспекту им. газеты «Красноярский рабочий». С 1983 года галерея получила статус музея.
В настоящее время музей располагает тремя помещениями, расположенными в разных частях города. Экспозиция русского искусства XVIII – начала XX веков размещена в бывшем особняке В.Н.Гадаловой. Это здание было построено в 1909 году на земельном участке, принадлежавшем крупному красноярскому купцу и меценату Петру Ивановичу Гадалову, по проекту архитектора В.А.Соколовского и при участии скульптора А. Попова. Особняк строился для жены П.И. Гадалова, который использовался ею для торжественных приемов.
Здание музея является памятником архитектуры г. Красноярска и имеет характерные черты стиля модерн. В этом особняке В.Н. Гадалова принимала среди прочих гостей всемирно известного путешественника норвежца Фритьофа Нансена, в период с 12-16 сентября 1913 года о чём свидетельствует памятная доска установленная на здании.
