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

Для размещения экспозиции была выбрана Дмитриевская башня нижегородского кремля. Она была отреставрирована «в древнем виде» и приспособлена под музей архитектором и археологом Н. В. Султановым и инженером П. П. Малиновским. Работы по реставрации и организации музея частично финансировались Городской думой. Но в основном это делалось на частные пожертвования граждан, так горячо было желание нижегородцев иметь в своем городе художественный музей. Торжественное открытие нового музея, приуроченное к проведению в Нижнем Новгороде Всероссийской художественно-промышленной выставки, состоялось 25 июня (7 июля) 1896 года. Объединенный музей получил название «Нижегородский городской художественный и исторический музей». Виды первой экспозиции запечатлены на фотоснимках знаменитых нижегородских фотографов М. П. Дмитриева и А. О. Карелина.

Музей несколько раз менял адреса. Покинув Дмитриевскую башню, музей расположился в здании Дворянского собрания на ул. Большой Покровской, а затем в особняке купца С. М. Рукавишникова. В 1924 году художественный отдел Нижегородского городского художественного и исторического музея разместился в национализированной усадьбе купца Д. В. Сироткина.

В 1934 году произошло официальное разделение исторического и художественного отделов городского музея. К этому времени окончательно сформировались основные разделы коллекции, стала развиваться система научного описания, учета и хранения произведений. Сложился основной историко-хронологический принцип экспонирования.

С 1992 года основная часть коллекции музея разместилась на территории кремля в здании Дома военного губернатора.

Сегодня музей занимает три здания. Экспозиция отечественного искусства представлена во Доме военного губернатора в кремле, экспозиция западноевропейского искусства располагается в доме Дмитрия Сироткина на Верхневолжской набережной, экспозиция искусства XX века на площади Минина и Пожарского.