The beginnings of the present-day Wien Museum date back to the 1860s, when the city council established a commission for municipal collections responsible for the acquisition and financing of objects for a future city museum. The museum was to collect "all valuable mementos of the history and cultural life of Vienna" and to make them accessible to the public. During the World's Fair in Vienna in 1873, the Städtisches Waffenmuseum (Municipal Weapons Museum), successor to the Bürgerliches Zeughaus, opened a historical collection in the city centre and at the Städtisches Pädagogium in Hegelgasse 12. Both undertakings attracted a large number of visitors and were a financial success, prompting the municipal council to approve the founding of a historical museum of the city of Vienna. In 1874, the Weapons Museum was merged with the Vienna municipal and provincial archive. It took until 1887, however, for a formal decision to be adopted by the council. In 1888, the Historisches Museum finally opened on premises in Vienna town hall. It included the Vienna city library and municipal archive (today Wiener Stadt- und Landesarchiv), which became a separate institution the following year, on 25 June 1889. On 12 July 1904, the Historisches Museum and Stadtbibliothek (today Wienbibliothek im Rathaus) were merged in a department also known as the Städtische Sammlungen. During the First World War, the museum was closed and some of the premises used by departments deemed necessary for the war effort, with the objects being stored together in a few rooms. In July 1917, the museum reopened in the premises available to it. Between the wars no real changes took place.

After the annexation of Austria to the German Reich in March 1938, the museum was taken over by the Nazi authorities and the staff checked for their political reliability and "race" categorization. They were obliged to swear an oath of allegiance to Adolf Hitler. As Oskar Katann, director since 1936, was deemed politically unreliable, he was retired in November 1938 and replaced by his former deputy Karl Wagner. At the same time, the municipal library became a separate entity headed by Ferdinand Müller. With the restructuring of the city administration, deputy mayor Hanns Blaschke became head on 22 September 1938 of the newly established Group VIII responsible for culture, and hence the direct supervisor of the museum and library directors. Thereafter, both Blaschke and Reichsstatthalter Baldur von Schirach, who wished to be informed in advance of new acquisitions by the Städtische Sammlungen, intervened directly in the museum's affairs. As a classic general museum, municipal department and museum in the Reichsgau of Vienna, it played an important role in the expropriation of art works belonging to Jewish inhabitants. It was well endowed financially and could therefore participate actively in the many auctions of property expropriated by the Nazis. Moreover, as the only museum on the mailing list of Municipal Department 50, which issued securing orders, it was well informed about artworks belonging to Jewish collectors. The Städtische Sammlungen issued "wish lists", which were passed on to the Zentralstelle für Denkmalschutz (Central Monument Protection Authority), for consideration when looted artworks were distributed.

The air raids on Wiener Neustadt in August 1943 made it clear that Vienna was now also in great danger. The museum was closed for the duration of the war. The storage of objects in sixteen locations in Lower Austria (Schloss Glaswein, Grusbach, Kartause Gaming, Kirchstetten, Pfarrhof Klein-Engersdorf, Schloss Laudon, Kartause Mauerbach, Schloss Niederleis, Pfarrhof Pulkau, Schloss Purgstall, Schloss Schönborn, Schloss Seefeld, Burg Stixenstein, Schloss Thalheim, Schloss Waidhofen and Schloss Wald) and some depots in Vienna (Hofburg, Teinfaltstraße, Augustinerkeller and Augustinerkirche), which had been planned since 1941, now began. The removals were completed in early 1944. In January 1944, the Clock Museum at Schulhof 2 in the 1st district was closed. The Roman Museum at Rainergasse 15 in the 4th district was destroyed in an air raid in February 1945. At the end of the war, some of the depots were plundered by Red Army soldiers, retreating German troops and civilians, and a considerable number of objects were lost.

Seven restitution laws were passed in post-war Austria. Of the twenty-nine restitution applications during this time, twenty had a positive outcome, and the applicants recovered most of their possessions, although in some cases only on condition that they bought them back at the price paid at the time, even though the Historisches Museum at the time had paid the Dorotheum rather than to the original owners. This was the case with Ferdinand Bloch-Bauer, whose descendants were only given back a porcelain object acquired by the museum in an auction at the Dorotheum after they had paid back the purchase price at the time.

Systematic and active provenance research commenced in 1998 at the instigation of Peter Marboe, municipal councillor for cultural affairs. The decision of the Vienna city council of 29 April 1999, modelled on the Federal Law on the Restitution of Art Objects from Austrian Federal Museums of 4 December 1998 (Art Restitution Act, BGBl I 181/1998), obliged the Museen der Stadt Wien to return artworks and cultural objects to their original owners or legal successors. An amendment to the decision on 29 April 2011 extended the validity to legal transactions according to Section 1 of the Federal Law of 15 May 1946 (BGBl. 106/1946) concluded between 30 January 1933 and 8 May 1945 in the territory governed by the German Reich outside the Republic of Austria. In the second instance, the word "without payment" was deleted to cover the restitution of eligible artworks and cultural objects that had been purchased by the city of Vienna under the Export Prohibition Act after 8 May 1945, insofar as there was a demonstrable close connection between the restitution proceedings, export prohibition and purchase. By 2017 over 3,000 objects from 50 collections had be restituted to the following collectors: Bernhard Altmann, Stefan Auspitz-Artenegg, Richard Beer-Hofmann, Josef und Auguste Blauhorn, Ferdinand Bloch-Bauer, Viktor Blum, Oscar Bondy, Karoline Broch, Laura Broch, Adele Duschnitz, Ernst Egger, Hanns Epstein, Friedrich Fischl, Hanns Fischl, Josef Isidor Fleischner, Siegfried Fuchs, David Goldmann, Alexander Grosz, Moriz Grünebaum, Herbert M. Gutmann, Leo and Helene Hecht, Alfred Hofmann, Josef Hupka, Jewish Institute for the Blind on Hohe Warte, Bruno Jellinek, Hans Klinkhoff, Wilhelm Viktor Krausz, Ernst Moriz Kronfeld, Lederer family, Mautner family, Ignaz Pick, Emil Politzer, Gisela and Ernst Pollack, Max Pollak, Franz and Melanie Popper, Adolf Guido Redlich (Adolphus Redley), Oskar Reichel, Heinrich Rieger, Heinrich Rothberger, Alphonse and Louis Nathaniel Rothschild, Franz Ruhmann, Ignaz and Clothilde Schachter, Paul Schwarzstein, Josef Simon, Strauß-Meyszner, Strauß-Simon, Josef Thenen, Josef Ungar, Charles Weinberger, Leopold Weinstein, Marianne Wengraf and Ella Zirner.