У 1999 році серед заходів з нагоди святкування 1100-річчя Полтави президент України Леонід Кучма взяв участь у відкритті новозбудованої галереї мистецтв на вулиці Фрунзе,5 (нині Європейська). Це установа культури нового зразка з просторими залами, холом, анфіладами, прес-центром на 70 місць і зимовим садом загальною площею понад 2 тис. кв.м.
Журнал «Архітектура і престиж» за 2000 рік так написав про цю споруду: «Ініціаторами й інвесторами будівництва галереї мистецтв виступили Національна спілка художників та Фонд підтримки талановитих дітей, голова якого – міський голова Анатолій Кукоба. Досі в Полтаві був один художній музей і жодної галереї. Архітектору з Полтави Юрію Олійнику захотілося знайти таке архітектурне рішення, яке продовжувало б традиції українського бароко. Від улюблених автором ковніровських палат у Лаврі до двохповерхового будинку вчителя танців Жемшерова, розташованого праворуч галереї мистецтв – пам’ятки архітектури 1814 року. Ці риси відобразилися в м’якій лінії фронтону, загальному малюнку фасаду, формі вікон. У комплексі кілька виставкових зал: на першому поверсі музей (300 кв. м) з депозитарієм (200 кв. м) і виставкова зала (45 кв.м), на другому поверсі – велика (486 кв. м) і мала (184 кв. м) експозиційні зали, павільйони на терасах і балкони загальною площею 370 кв. м та галерея для скульптури 30 кв. м».
Уперше у ЗМІ про будівництво галереї мистецтв згадується у 1994 році. Головний архітектор Полтави Олександр Ротманський в інтерв’ю газеті «Вечірня Полтава» на запитання кореспондента, які нові заклади культури мають з’явитися найближчим часом у місті, відповів: «Є дуже велике бажання спорудити в місті картинну галерею. Місце для неї вже визначене на вулиці Фрунзе, поряд з дитячою спортивною школою».
Сама ж ідея створення галереї мистецтв у Полтаві зародилася ще у 1989 році. Згадує автор проекту архітектор Юрій Олійник: «Ідею створення у Полтаві галереї мистецтв запропонував мій однокласник, який, на жаль, пішов з життя, народний художник України Володимир Колесніков. Разом з колегами він створив товариство мистецтв, відкрив галерею «Парсуна» на Клубному провулку,4. Тоді й народилася думка про створення великої полтавської галереї. Колесников прийшов до мене з пропозицією виконати проект майбутньої споруди, це було на початку 1989 року. Тоді я працював у державному проектному інституті «Діпрогеобуд». Щоб полтавська галерея мала достойний рівень, потрібно було познайомитися з передовими зразками. Тому після перших ескізів поїхав подивитися в Москву на Третьяковську галерею. Особливу увагу приділив ознайомленню з новим інженерним корпусом цієї споруди. Там у величезних залах розміщені роботи, які потребують особливого догляду, створене відповідне освітлення, існують додаткові приміщення. З колегами дивилися, де і як зберігаються картини великих художників (це приміщення зветься депозитарій). На основі побаченого розробили проект з урахуванням побажань нашого замовника ТВО «Мистецтво», щоб у майбутній споруді були творчі майстерні, арт-кафе, депозитарій, карантинний бокс, виставкові зали із сучасним конвенційним обладнанням, щоб витримувалися терміни по волозі й теплу. За період підготовки проекту я став директором творчо-проектного підприємства «Перспектива». Робочі креслення галереї вже почали розробляти в цій фірмі разом з інженером-конструктором Сергієм Палієм, сантехніком Галиною Купрій та іншими фахівцями. Коли постало питання реалізації, то в «Мистецтва» коштів не вистачало і на допомогу прийшов «Фонд підтримки талановитих дітей», який очолював Анатолій Кукоба. Він спочатку попросив скласти кошторис з розрахунками термінів будівництва представників турецької фірми «Атлант», яка зводила споруду для банку в Полтаві. Після отримання результатів… вирішив передати справу АТ «Полтаватранс-буд». Своє рішення прокоментував так: «Вони, може, і гарні будівельники, але не місцеві, а з наших у разі недоробок можна спитати і розібратися». Урочисто заклали камінь і почалися роботи, але по ходу реалізації проекту постало питання про комерційну складову від функціонування галереї. Виставки, які там планували проводити, значного прибутку не принесуть, тому вирішили добудувати до галереї готель. Оскільки Анатолій Кукоба, який керував процесом, за фахом теплотехнік, він запропонував установити котельну на даху. Також під час реалізації проекту відбулися деякі зміни: з’явилася зала дитячої творчості ім.Саші Путрі, відмовилися від арт-кафе. Але головне те, що художній музей не планували переводити в галерею. Варто згадати вагому роль в оформленні простору всередині галереї, яке виконав знаний в Україні художник Олександр Левадний».
У зв’язку з незадовільним технічним станом колись наспіх відремонтованого будинку (технічний висновок Полтавської філії Держбуд України «НДІпроектреконструкція», лютий 2000 року) Полтавський художній музей ухвалою Полтавської міської ради від 11 квітня 2000 року переведено в приміщення галереї мистецтв на вулиці Європейській. Тут він отримав постійну прописку, розмістивши експозицію у трьох анфіладах першого поверху, а фонди – у спеціально обладнаному фондосховищі. У 2008 році Полтавський художній музей (галерея мистецтв) отримав ім’я Миколи Ярошенка.
