Galerija domuje v najožjem centru mesta v modernistični zgradbi, ki jo je leta 1971 arhitekt Adi Miklavc (1937-2002) postavil ob bok nosilnim zgradbam mestnega jedra na Titovem trgu. Začetki segajo v leto 1975. V sklopu Kulturnega centra Ivan Napotnik je bila ustanovljena tudi galerija leta 1976. Prvi galerijski zbirki (Lojzeta Perka in Sodobno slovensko slikarstvo) sta bili postavljeni v Knjižnici Kulturnega centra Ivan Napotnik Velenje, znotraj katere je bil tudi razstavni prostor. Po izselitvi knjižnice leta 2005 je Galerija pridobila celotni prostor v zgradbi na Titovem trgu 5. 2008 je bil ustanovljen Javni zavod Galerija Velenje.
Programsko in strokovno zastopa predvsem sodobno umetnost Šaleške, Zgornje Savinjske doline, Slovenije in Evrope. Usmerjena je v razstavno, raziskovalno, dokumentacijsko in pedagoško delo. Zbirka Galerije Velenje se s skoraj tisoč deli uvršča med pomembnejše likovne zbirke v Sloveniji in poleg slikarstva in kiparstva slovenske moderne in sodobne umetnosti, vključuje tudi dela študentov ALUO (1992-2007), grafiko, fotografijo in risbe ter mednarodno zbirko slikarstva.