Bereits in den 1910er Jahren gab es vereinzelte Ausstellungsaktivitäten im Bereich der Bildenden Kunst in Gelsenkirchen, beispielsweise mit Werken der Künstlergruppe „Niederrhein“ (1914) oder von Adolf Menzel (1916). Nach dem Ersten Weltkrieg wurden durch den 1921 gebildeten Städtischen Museumsausschuss, unterstützt durch die Vereinigung Westfälischer Künstler und Kunstfreunde, diese Aktivitäten ausgebaut und institutionalisiert: Errichtung einer „Städtischen Gemäldegalerie“ an der Markstraße 14 (heute von-Oven-Straße) mit regelmäßigen Kunstausstellungen von lokalen und nationalen Künstlern, z. B. der Worpsweder Künstler; Einrichtung von Ausstellungsräumen im Georgshaus an der Ahstraße, wo auch Magazinmöglichkeiten bestanden. So konnte die Stadt auch eine Kunstsammlung aufbauen, die bis 1930 Arbeiten u.a. von Chagall, Kubin, Dürer, Rembrandt, Marées und Pankok aufwies. Diese Aktivitäten wurden durch das nationalsozialistische Kunstverständnis und die Aktion „Entartete Kunst“ 1937 erheblich beeinträchtigt, weitere Teile der Sammlung wurden durch die Bombardierungen im Zweiten Weltkrieg vernichtet. Nur noch kleine Teile der Sammlung vor 1945 sind im Museum erhalten.
Im Jahr 1950 fasste die Stadt Gelsenkirchen den Beschluss, die schon 20 Jahre zuvor begonnenen Aktivitäten wieder aufzugreifen und nun systematisch eine eigene städtische Kunstsammlung unter fachkundiger Leitung aufzubauen. Zunächst fanden die künstlerischen (und auch naturkundlichen) Schätze ihren Platz neben der heimatkundlichen Sammlung in den Räumen des Heimatmuseums an der Breddestraße und in der daneben stehenden umgebauten Pöppinghaus-Villa an der Horster Straße. Der Bau des Musiktheaters im Revier (MiR), an dem Künstler wie Yves Klein und Jean Tinguely beteiligt waren, beflügelte das Engagement für die Kunst in Gelsenkirchen. In der Folge des kulturellen Höhenflugs kam es zu Ankäufen, Schenkungen und Dauerleihgaben zahlreicher Werke für die Stadt. Durch den ständigen Zuwachs wurde immer deutlicher, dass die städtische Sammlung mehr Platz benötigte.
Nach Plänen des Architekten Albrecht E. Wittig wurde 1982 mit dem Neubau an der Horster Straße begonnen, der die alte Villa durch eine Brücke mit den neuen Ausstellungsräumen verbindet. Allerdings wurde in diesem ersten Bauabschnitt nur ein reduziertes Raumprogramm realisiert. Aufgrund der angespannten Finanzlage der Stadt musste die Realisierung des zweiten Bauabschnitts bis heute zurückgestellt werden. Das „neue Museum“ wurde 1984 an der Horster Straße 5 - 7 eröffnet. Im Zuge der Vergrößerung und Modifizierung des Sammlungsbestands widmet sich das Museum seit 1993 ausschließlich der Kunst. Am 27. August 2008 beschloss der Kulturausschuss die Umbenennung in "Kunstmuseum Gelsenkirchen".
Bereits seit 1962 verzichtet das Kunstmuseum bewusst darauf, Eintrittsgelder zu erheben, damit auch breitere Bevölkerungsschichten Zugang zur Kunst erhalten.