Stolz was born of musical parents in Graz. His father was a conductor, his mother a concert pianist, and he was the great-nephew of the soprano Teresa Stolz. At the age of seven, he toured Europe as a pianist, playing Mozart. He studied at the Vienna Conservatory with Robert Fuchs and Engelbert Humperdinck. From 1899 he held successive conducting posts at Maribor (then called Marburg), Salzburg and Brno before succeeding Artur Bodanzky at the Theater an der Wien in 1907. There he conducted, among other pieces, the first performance of Oscar Strauss's Der tapfere Soldat (The Chocolate Soldier) in 1908, before leaving in 1910 to become a freelance composer and conductor. Meanwhile, he had begun to compose operettas and individual songs and had a number of successes in these fields.
After serving in the Austrian Army in World War I, Stolz devoted himself mainly to cabaret, and moved to Berlin in 1925. Around 1930, he started to compose music for films, such as the first German sound film Zwei Herzen im Dreivierteltakt (Two Hearts in Waltz Time), of which the title-waltz rapidly became a popular favourite. Some earlier Stolz compositions, such as "Adieu, mein kleiner Gardeoffizier" from his operetta Die lustigen Weiber von Wien, became known to wider audiences through the medium of film, after it was interpolated into Im weißen Rößl (The White Horse Inn).
The rise of Nazi Germany led Stolz to return to Vienna, where his title-song for the film Ungeküsst soll man nicht schlafen gehn was a hit. He remained active in Berlin as well. He used to travel by car between the two cities, so he smuggled Jews and political refugees across the German-Austrian border in the trunk of his limousine. He managed to do so 21 times. Then came the Anschluss, and he moved again, first to Zürich and then to Paris, where in 1939 he was interned as an enemy alien. With the help of friends he was released and in 1940 made his way to New York.
In America, Stolz achieved fame with his concerts of Viennese music, starting with "A Night in Vienna" at Carnegie Hall. As a result, he received many invitations to compose music for shows and films, and he received two Academy Awards nominations: "Waltzing in the Clouds" for Spring Parade was nominated for Best Original Song in 1941, and his score for It Happened Tomorrow was nominated for Best Dramatic or Comedy Picture Score in 1945.
In 1946 Stolz returned to Vienna, where he lived for the rest of his life. In the 1960s and 1970s he made numerous recordings of operettas by composers such as Johann Strauss, Franz Lehár, Emmerich Kálmán, and Leo Fall, whom he had known previously.
In 1952, he began to compose for the Vienna Ice Revue. He dedicated his first of 19 ice operettas ("Eternal Eve") to European Champion Eva Pawlik. In 1970, to mark his 90th birthday, he was made an Honorary Citizen of Vienna. He was also awarded Vienna's Grand Medal of Honour, being only the second musician ever to be so honoured (after Richard Strauss). He also appeared on a series of commemorative Austrian postage stamps.
In later years he used a baton inherited from Franz Lehár, which had been originally owned by Johann Strauss and contained Strauss's initials engraved in silver.
After his death in Berlin in 1975, Robert Stolz received the honour of a lying-in-state in the foyer of the Vienna State Opera House. He was buried near Johannes Brahms and Johann Strauss II in Vienna's Zentralfriedhof, and a statue to him was erected in the Wiener Stadtpark. A street is named after him - just off the Opernring in Vienna, close to the State Opera.
Robert Stolz was married five times. His first and second wives (Grete Holm and Franzi Ressel), were singers. His third wife was Josephine Zernitz and the fourth was named Lilli. His fifth wife Yvonne Louise Ulrich, called "Einzi" (1912-2004), was his manager until his death. She had one daughter from her first marriage, whom Robert Stolz adopted.
- Das Glücksmädel (1910)
- Der Tanz ins Glück (The Dance into Happiness) (1921)
- Im weißen Rößl (The White Horse Inn) (1930), jointly with Ralph Benatzky
- Wenn die kleinen Veilchen blühen (When the Little Violets Bloom or Wild Violets) (1932)
- Der verlorene Walzer, a stage version of the film Zwei Herzen im Dreivierteltakt (1933)
- "Servus Du" (1912) words by Benno Vigny
- "Wien wird erst schön bei Nacht" words by Wilhelm Sterk
- "Im Prater blühn wieder die Bäume" words by Kurt Robitschek
- "Das ist der Frühling in Wien" words by Arthur Rebner
- "Du, du, du sollst der Kaiser meiner Seele sein." (1916)
- "Hallo, du süsse Klingelfee" (1919) words by Arthur Rebner
- "Salome, schönste Blume des Morgenlands" (1920) words by Arthur Rebner
- "Ich will deine Kameradin sein" words by Walter Reisch
- "Die ganze Welt ist himmelblau" words by Robert Gilbert
- "Zwei Herzen im Dreivierteltakt" (Two Hearts in 3/4 Time) words by Walter Reisch 
- "Das Lied ist aus" (Frag nicht warum) (1930) with words by Walter Reisch from the 1930 film Das Lied ist aus directed by Géza von Bolváry
- "Wiener-Café" (Waltz)
- "Adieu mein kleiner Gardeoffizier" words by Bruno Balz
- Two Hearts in Waltz Time (1930)
- The Merry Wives of Vienna (1931)
- The Prince of Arcadia (1932)
- A Man with Heart (1932)
- What Women Dream (1933)
- My Heart Calls You (1934)
- Two Hearts in Waltz Time (1934)
- Spring Parade (1934)
- The Gentleman Without a Residence (1934)
- Circus Saran (1935)
- Heaven on Earth (1935)
- The Charm of La Boheme (1937)
- Who's Your Lady Friend? (1937)
- The White Horse Inn (1952)
- Come Back (1953)
Honours and awards
- 1934: Venice International Film Festival: Great Medal (Best Musical) for Spring Parade
- 1941: Academy Award nomination (Best Original Song) for the song Waltzing in the clouds from Spring Parade
- 1945: Academy Award nomination (Best Musical) for It Happened Tomorrow
- 1946: Professor Honoris Causa by the Austrian Government
- 1947: Citizens charter of the city of Vienna
- 1962: Great Cross of the Order of Merit of the Federal Republic of Germany
- 1964: First honorary member of the Vienna Volksoper
- 1965: Ring of Honour of the City of Graz
- 1968: Honorary Ring of Styria
- 1969: Film Award for many years of excellent work in German films
- 1969: Ring of Honor at the Bregenz Festival
- 1970: Honorary Citizen of the City of Vienna
- 1970: Cultural honor letter of Passau
- 1970: Honorary Citizen of the City of Graz
- 1970: Honorary Medal of the City of Rotterdam
- 1970: Ring of Honour of Gesellschaft für musikalische Aufführungs- und mechanische Vervielfältigungsrechte
- 1970: Austrian Decoration for Science and Art
- 1970 Honorary Medal of the City of Jerusalem
- 1971 Jerusalem Medal (for the flight assistance to Jewish citizens)
- Stanley Sadie Ed. (2002) The New Grove Dictionary of Opera, Oxford University Press ISBN 1-56159-228-5
- "Johann Strauss Society: Robert Stolz". Johann Strauss Society of Great Britain. Retrieved 2008-10-01.
- The Oxford Dictionary of Music 2nd ed. (1995), Oxford University Press ISBN 0-19-869162-9
- "Trauer in Wien:Witwen-Legende Einzi Stolz ist tot" ("Mourning in Vienna:Legendary Widow 'Einzi' Stolz is Dead") in News (28 January 2004), accessed 25 December 2010
- "Reply to a parliamentary question" (pdf) (in German). p. 293. Retrieved 23 November 2012.
- Bakshian, A. 1983. The Barbed Wire Waltz : the memoirs of the Last Waltz King Melbourne: Robert Stolz Publishing. ISBN 0-9592017-0-X