Після трагічної загибелі художника Василя Верещагіна під час російсько-японської війни на його честь у 1914 році в Миколаєві відкрили музей. Завдяки клопотанням видатних митців та князів виділили приміщення колишнього палацу Потьомкіна. А основою стала колекція картин Верещагіна, отримана з музею Олександра ІІІ, меблі з кабінету художника. Мольберт, дві палітри, китайську вазу, килим та багато фотознімків з його картин передав син митця у тому ж 1914-му.

За словами начальника відділу інформації та використання документів Державного архіву Миколаївської області Марини Мельник, колекція Верещагіна складалася майже з 400 картин та етюдів.

З Петербурзької художньої академії 1914 року отримано картини Айвазовського «Пушкін на березі Чорного моря», Боголюбова «Венеція», Громме «Лазарет у Севастополі», Алілова «Іоанн Грозний на прогулянці», Сергієва «Картопляне поле», Свєрчкова «Голова коня», Маковського «Букініст», Віллєвальде «Взяття Гуніба», Крачковського «Гроза» та ін. Звідти ж було надано музеєві скульптури, такі як Розумовського «Самсон і Даліла», Антокольського «Іоанн Грозний», Сергєєва «Св. Юлія», Беклемішева «Св. Варвара», та дві вази російського порцелянового заводу епохи Миколи І.

1917 року музей поповнився картинами з приватних колекцій Сенкевича та Кудрявцева: портретами Гольбейна та Бенуа, а також отримав вісім гобеленів, вісім бісерних вишивок, 15 експонатів зі слонової кістки, дві вази з оніксу, одну — з аметисту, 83 порцелянові вази і статуетки та 16 килимів. Пізніше колекцію музею поповнили скульптури Брега, Лієра, Сімонетті, Канови, Ботеллі та ін.

У 1924 році з Очакова надійшла колекція картин мариніста Руфіна Судковського, передана братом художника. Наступного року дружина художника Мурзанова подарувала музеєві 15 картин чоловіка, музей також придбав 20 його картин. 1935 року після закриття миколаївського костьолу до музею надійшло 75 картин, 25 вітражів та 30 скульптур, копії Рафаеля, Мурільйо, Домініко-Феті, Дольчі.

У березні 1986 року було відкрито нову експозицію Миколаївського художнього музею ім. В.В. Верещагіна у десяти залах загальною площею у 1133 квадратні метри. Музей уже мав свої відділення, а саме музей ім. В. Судковського в Очакові та музей ім. Є. Кібрика у Вознесенську.

На своє сторіччя музей імені В.В. Верещагіна провів кілька урочистих заходів. Так, відкрилося традиційне, вже 12-те Верещагінське бієнале. Проведення обласного бієнале дитячої творчості присвятили одночасно трьом круглим датам: 100-річчю музею імені Верещагіна, 200-річчю з дня народження Тараса Шевченка і 225-річчю заснування Миколаєва. Девізом конкурсу стала його назва: «Світ навколо тебе». Всього на виставку надійшла 371 дитяча робота, а участь взяли майже три десятки миколаївських гуртків та студій образотворчого мистецтва. Серед конкурсантів були діти з Очакова, Южноукраїнська, Первомайська, вихованці шкіл та гуртків Єланецького і Снігурівського районів області.

Нагороджував переможців президент Національної Академії мистецтв України Андрій Чебикін, який зазначив: «Всі діти по суті прекрасні художники. Особливо ті, хто любить це заняття». І хоча всі учасники конкурсу розподілені на три вікові групи, головний приз вирішили вручити маленькій Валерії за картину «Верещагін за роботою».

Андрій Чебикін нагородив і дорослих митців. Зокрема, золоту медаль академії він вручив директору музею ім. В.В. Верещагіна Сергію Рослякову та голові Миколаївської обласної спілки художників Олегові Приходьку.

Як зазначив голова Миколаївської обласної ради Тарас Кремінь, «ми сьогодні повинні не тільки привітати колектив музею, а й взяти на себе зобов’язання підтримувати його надалі, і в наступні 100 років. Про нас судитимуть по тому, як ми ставилися до культури».