Роберт Штольц был двенадцатым ребёнком в семье композитора и дирижёра Якоба Штольца и его жены Иды (урожд. Бонди), пианистки и учительницы музыки. Близким другом отца был Иоганн Брамс, который, услышав игру маленького Роберта на фортепьяно, предсказал тому блестящую музыкальную карьеру. Роберт изучал музыку в Граце, Берлине и Вене. В 1896 году, в возрасте 16 лет, он закончил Венскую консерваторию. В 1897 он был оперным концертмейстером в Городском театре Граца, в 1899 году капельмейстером в Марбурге, затем в Драве и в 1902 году в городском театре Зальцбурга.
Во время Первой мировой войны с 1914 по 1918 год Штольц служил в австрийской императорской армии, в том числе в качестве капельмейстера четвёртого пехотного полка.
В начале 1920-х годов Роберт Штольц стал владельцем театра варьете «Max und Moritz». Большие расходы на содержание театра практически разорили Штольца. К тому же у театра не было лицензии. Впоследствии затею с театром Штольц назвал «самым большим фиаско во всей моей карьере». Спасаясь от кредиторов, Штольц переехал в 1924 году в Берлин. Через два года, в 1926 году он вернулся в Вену.
После прихода к власти национал-социалистов в 1933 году, Р. Штольц за передними сиденьями своего лимузина вывез тайком несколько евреев и политически преследуемых в Австрию. Всего он совершил 21 поездку. В 1938 году, после аншлюса Штольц уехал из Австрии из-за неприятия идеологии национал-социализма. Через Цюрих он прибыл в Париж. 30 ноября 1939 года Штольц был арестован французской полицией и интернирован в лагерь «Colombe», как «враждебный иностранец». Это случилось из-за того, что четвёртая жена Роберта Штольца, некая Лилли, оставив его, похитила все драгоценности, его документы и вид на жительство. В лагере 59-летний Штольц заболел пневмонией. Он был спасен благодаря случайному знакомству с девятнадцатилетней дочерью французского банкира Ивонной Луизой Ульрих, которая училась в Париже на юриста. Узнав, что Штольц был интернирован, она собрала несколько тысяч франков на взятку для освобождения композитора. Впоследствии она стала его пятой женой. Парижские эмигранты дали ей прозвище «Айнци» «Einzi», поскольку она была единственной (einzige), кто предложил Штольцу помощь.
В 1940 году Штольц эмигрировал в Нью-Йорк, где прожил все военные годы. 28 августа 1941 года Штольца лишили немецкого гражданства, его имущество было изъято.
30 октября 1946 года Роберт и Айнци Штольц вернулись в Вену. Они стали первыми гражданскими лицами, которым разрешили перелёт из США в Австрию. У них были визы за номером 1 и 2. В Венском международном аэропорту в их честь был устроен торжественный приём, на котором присутствовал мэр Вены Теодор Кернер. В 1947 году австрийское правительство присвоило Штольцу звание профессора Honoris causa.
Роберт Штольц умер 27 июня 1975 года. Он похоронен на Венском центральном кладбище.
Роберт Штольц состоял в браке пять раз. Его первой женой была актриса Грета Хольм, второй — певица кабаре Франци Рессель. В 1923 году он вступил в брак со своей третьей женой Джозефин Церниц. Этот брак распался через год. Его четвертая жена Лилли оставила его в 1939 году в Париже. Пятой женой композитора стала Ивонна Луиза Ульрих («Айнци», Einzi Stolz; ум. 18 января 2004).
Роберт Штольц — автор более чем двух тысяч песен и вальсов, он написал музыку более чем к 60 опереттам и 100 кинофильмам. Он считается последним мастером Венской оперетты. Многие отрывки из его произведений известны и популярны до сих пор.
Р. Штольц дебютировал как композитор 3 марта 1903 года в городском театре Зальцбурга с опереттой «Прекрасная Лорхен». После ангажемента в Немецком театре в Брюнне он был музыкальным руководителем в Венском театре с 1905 по 1917 год. В этом качестве 30 декабря 1905 года он осуществил премьеру «Весёлой вдовы» (Die lustige Witwe) Франца Легара.
Кинематограф открыл перед композитором новые возможности. В 1913 году Штольцу было поручено сочинить музыку для австрийского немого фильма «Дядюшка-миллионер» («Der Millionenonkel»). Вопреки обычной музыке для кино того времени, которая исполнялась одним пианистом, произведение Штольца исполнял большой оркестр.
В послевоенные годы композитор занимался, в основном, написанием музыки для кабаре, пополняя, главным образом, репертуар своей жены Франци Рессель. В 1919 году он совместно с Отто Хейном (Otto Hein) написали песню «Hallo, du s?sse Klingelfee», ставшую весьма популярной, она была переведена на русский, чешский, английский, французский и итальянский языки. Штольц — первый европейский автор фокстрота.
В 1925 году в берлинском «Кабаре комиков» Штольц поставил оперетту «Снежная сказка». В начале 1930-х годов он начал сочинять музыку для звукового кино, например, для первого немецкого звукового фильма «Два сердца в три четверти такта», одноимённый вальс из которого очень быстро стал популярным. С 1930 по 1932 год Роберт Штольц сочинил музыку к семнадцати фильмам.
Находясь в эмиграции в Париже, Роберт Штольц продолжил композиторскую деятельность. Там он сочинил оперетту «La montagne bleue». Первые попытки Штольца заявить о себе как о композиторе в США потерпели неудачу. Однако он получил приглашение от Нью-Йоркского филармонического оркестра заменить дирижёра Бруно Вальтера на концерте произведений Иоганна Штрауса «Ночь в Вене» в Карнеги-Холле. Хотя у Штольца не было никакого опыта в дирижировании симфоническим оркестром, концерт прошёл с большим успехом. Штольцу стали поступать предложения от компаний грамзаписи и радиостанций на сочинение музыки для фильмов, театральных постановок и концертов. Благодаря тому, что супруга Штольца Айнци пригласила на концерт менеджера крупнейшего американского концертного агентства, состоялся гастрольный тур оркестра по США концертной программой «Ночь в Вене». Второй концерт, на котором исполнялись произведения Иоганна Штрауса, Франца Легара, Оскара Штрауса, Имре Кальмана и Роберта Штольца, прошёл при аншлаге, собрав 20 000 зрителей.
Роберту Штольцу дважды присуждалась премия «Оскар» за музыку к фильмам «Весенний вальс» (Spring Parade; 1941) и «Это случилось завтра» (It Happened Tomorrow; 1944).
С 1950 по 1970 год Штольц был неотъемлемой частью австрийской и европейской музыкальной жизни. В 1951 году по его оперетте «Der Tanz ins Gl?ck» режиссёром Альфредом Штёгером был снят одноимённый художественный фильм. В том же году в Лондоне был поставлен мюзикл «Rainbow Square», а в Вене оперетта «Das Gl?cksrezept». В 1952 году Штольц создал оперетту «Вечная Ева» (Die ewige Eva) — первую из 19 ледовых оперетт для Венского балета на льду. В 1953 году аркадный двор венской ратуши стал сценой для премьеры зингшпиля «Der liebe Augustin». Оперетта «Signorina» была поставлена в 1954 году в Нюрнберге. В 1955 году на экраны вышел фильм «Весенний парад», с участием Роми Шнайдер. Это был третий фильм на данный сюжет. Первый фильм «Весенний парад», для которого Роберт Штольц написал музыку, появился на киноэкране в 1934 году. Второй фильм на этот же сюжет, но уже под названием «Весенний вальс», вышел на экраны в 1940 году. В 1964 году композитор и либреттисты переделали киносценарий в оперетту. «Весенний парад» стала одной из самых популярных оперетт. Она с успехом ставилась не только в Австрии, но и во Франции, Бельгии. В 1957 году Штольц представил «Марш Организации Объединенных Наций», в 1958 году написал музыку к фильму «Im Prater bl?hn wieder die B?ume», в 1959 — к музыкальной комедии «Kitty und die Weltkonferenz». В 1962 году на фестивале в Брегенце была впервые поставлена оперетта «Trauminsel», в 1963 — музыкальная комедия «Ein sch?ner Herbst», либреттистом которой был австрийский писатель и театральный критик Ганс Вейгель. В 1965 году, в канун Нового года, Р. Штольц дирижировал в оперетте «Летучая мышь» И. Штрауса в Венском оперном театре. В 1967 году Штольц принимал самое непосредственное участие в праздновании столетия вальса Штрауса «На прекрасном голубом Дунае». В 1969 году в Брегенце на Боденском озере, превращённом в сцену, состоялась премьера произведения Штольца «Hochzeit am Bodensee».
Роберт Штольц увлекался филателией с детства. Этому увлечению способствовали мечты о посещении далёких стран, где можно увидеть яркие краски природы и экзотических животных. Будучи ребёнком со слабым здоровьем, Роберт не играл со сверстниками, а с удовольствием разглядывал марки, вырезанные для него матерью из многочисленной корреспонденции отца.
Начало коллекции почтовых миниатюр юного Роберта помогли положить отец и, часто бывавший в их доме, Иоганн Брамс, который подарил шестилетнему Штольцу пачку конвертов с различными марками. Отец давал Роберту разъяснения и советы по коллекционированию марок и систематизации коллекции. С годами увлечение Штольца марками не прошло, хотя его коллекция погибла в годы аншлюса Австрии. Вернувшись в Вену, он решил вновь заняться филателией. Помогали в этом друзья и многие почитатели таланта композитора. Штольц писал:
Эмигрировав в 1938 году во Францию и Англию, а затем в США, Штольц не смог вывезти с собой не только ряд неоконченных произведений, но и свою филателистическую коллекцию. По возвращении после войны в Вену, композитор обнаружил исчезнувшими оставленные им произведения, рукописи Брамса и Бетховена, подаренные отцом, и марки. Но вскоре Штольц возобновил собирание марок, на этот раз решив ограничиться австрийскими марками, в чём ему помогали друзья и почитатели.
В 1970 году к 90-летнему юбилею композитора австрийская почта издала памятную марку, посвящённую самому известному произведению Штольца — оперетте «Два сердца в три четверти такта», впервые отметив не президента Австрии, а другого живущего человека — представителя искусства страны. В день издания, 11 сентября 1970 года, применялся специальный штемпель с портретом композитора. Двумя месяцами позже, когда Штольцу было присвоено звание Почётного гражданина Граца, применялся другой штемпель. На имя Р. Штольца пришли тысячи поздравлений от поклонников и друзей-филателистов. Всё это вдохновило композитора на создание «Филателистического вальса», посвящённого филателистам всего мира:
Создание «Филателистического вальса» было отмечено двумя австрийскими спецгашениями от 1 октября 1972 года и 26 мая 1973 года. Ноты вальса были помещены на почтовой марке Сан-Марино, посвящённой 100-летию со дня рождения композитора (Михель #1219; Скотт #994). Это произведение исполняют теперь на различных филателистических мероприятиях.
В 1972 году Роберт Штольц, по приглашению Айрин Лоуфорд (англ. Irene Lawford), президента международной филателистической ассоциации Philatelic Music Circle (PMC), стал её членом.
В мае 1975 года, на 95-летие автора «Филателистического вальса», австрийской почтой снова применялось спецгашение. За семь дней до своей смерти композитор писал:
Роберт Штольц запечатлён на множестве почтовых марках и специальных почтовых штемпелях. Помимо Австрии, почтовые марки с портретом композитора были выпущены в Западном Берлине, Сан-Марино, Парагвае, Уругвае, Венгрии и КНДР.
В 1979 году по предложению вдовы композитора Айнци Штольц PMC учредила ежегодную премию имени Роберта Штольца, которая присуждалась художнику за лучшую марку музыкальной тематики. Первое награждение состоялось в 1980-м, в год столетия композитора. Премия присуждалась до 1997 года.
Многие улицы и площади носят имя Роберта Штольца, ему установлены памятники. В Берлине имеется «Общество Роберта Штольца».
8 ноября 2006 года в Отделе нотных изданий и звукозаписей Российской национальной библиотеки (РНБ) в Санкт-Петербурге была открыта выставка, посвящённая жизни и творчеству Роберта Штольца. На выставке были представлены ноты и пластинки из фондов РНБ, а также филателистический экспонат «Мелодия одной жизни» члена Общества филателистов Санкт-Петербурга Елены Панькиной.