Музей является одним из старейших региональных музеев России. Инициатива его создания принадлежит двум художникам, заложившим основу собрания — профессору Академии художеств Николаю Андреевичу Кошелеву (1840–1918) и историческому живописцу Андрею Андреевичу Карелину (1866–1928), сыну известного нижегородского фотографа А.О. Карелина.
Официальное решение о создании музея было принято на заседании Городской думы 14 июля 1894 года. В ходе его организации городские власти решили объединить вновь создаваемый художественный музей с уже существовавшим историческим, так называемым «Петровским домиком».