Osnovan je 1948. godine donacijom rimskog novca, namještaja, oružja i umjetničkih slika koje je svom gradu poklonio dr. Antun Bauer. Muzej je s radom započeo u Zgradi diližansne pošte u staroj baroknoj jezgri, a 1966. preseljen je u Dvorac Eltz. Do 1991. Muzej je sadržavao fond od oko 50 tisuća eksponata što su činili četiri zasebna odjela: Zavičajni muzej, Zbirka Bauer, Spomen-muzej nobelovca Lavoslava Ružičke i Spomen-muzej II. kongresa KPJ.
Tijekom Domovinskog rata dvorac Eltz je pretrpio velika oštećenja, a zbirke koje su se tu čuvale također su stradale: dio je potpuno uništen, dio je nepovratno nestao, a dio je odvezen u Srbiju. Nakon dugogodišnjeg truda i diplomatskih aktivnosti Ministarstva kulture RH taj dio zbirke vraćen je u Vukovar 13. prosinca 2001. Potkraj 1992. godine osnovana je zbirka pod nazivom Muzej Vukovara u progonstvu i tako nastaje zbirka donacija hrvatskih, a potom i europskih, umjetnika za grad Vukovar. Do danas je u toj zbirci prikupljeno više od 1400 djela suvremene hrvatske i europske umjetnosti. Ova zbirka predstavlja početak kulturne obnove Vukovara i bit će stalno izložena u obnovljenom Dvorcu Eltz uz ostale muzejske zbirke.

Gradski muzej Vukovar danas djeluje u kompleksu Dvorca Eltz koji će, kad bude u cijelosti obnovljen, biti jedinstveni muzeološko-galerijski, znanstveni i multimedijalni centar u kojemu će se čuvati i prezentirati kulturna baština kao element nacionalnog identiteta i kontinuiteta života na ovom području.