Wo heute der Waldmüllerpark liegt, befand sich ab 1784 der katholische Communal-Friedhof Matzleinsdorf. Er entstand auf Anordnung Kaiser Josephs II., der die Schliessung aller Friedhöfe innerhalb des Linienwalls veranlasst hatte. 1879 wurde der Friedhof für weitere Bestattungen gesperrt. In den frühen 1920er-Jahren entschied die Stadt unter Bürgermeister Jakob Reumann, das Gelände in eine öffentliche Parkanlage umzuwandeln. Zahlreiche bekannte Persönlichkeiten waren hier bestattet; rund hundert von ihnen wurden exhumiert und am Rand des neuen Parks in einem Gräberhain wieder beigesetzt.
Zu ihnen gehören unter anderem Ludwig van Beethovens Bruder Johann, der Verleger Carl Haslinger und der Biedermeiermaler Ferdinand Georg Waldmüller, nach dem der Park benannt wurde. Andere, wie Christoph Willibald Gluck oder Antonio Salieri, erhielten neue Ruhestätten in Ehrengräbern am Zentralfriedhof. Teile der alten Friedhofsmauer sind bis heute erhalten. Auf dem Areal der früheren Friedhofsgärtnerei entstand von 1923 bis 1925 ein Kindertagesheim nach Plänen von Hugo Mayer, gedacht als Zufluchtsort für Arbeiterkinder in der von Not geprägten Nachkriegszeit.
Der Park zwischen Südbahntrasse, Gudrunstrasse und Landgutstrasse ist heute ein geschätzter Treffpunkt für die Bewohner des Quartiers.