Robert Stolz épouse Grete Holm à Brno. En 1905, passionné par les techniques nouvelles, il enregistre sur disque Edison, avec l'étoile de l'Opéra de Vienne Selma Kurz, quelques airs de la « Flûte enchantée » de W.A. Mozart. La même année, il est nommé, à l'âge de 25 ans, premier chef d'orchestre au célèbre théâtre « An der Wien  » et dirige, le 30 décembre 1905, la première d'une œuvre d'un jeune compositeur de 35 ans, Franz Lehár, et qui deviendra par la suite un immense succès mondial :  « La Veuve Joyeuse ».

« Vous savez que c'est moi qui ait dirigé, en 1905, au théâtre « An der Wien », la Première de la Veuve Joyeuse, qui ne fut pas accueilli favorablement à ce moment-là ... Est-ce que c'est de la musique ? me demandait-on ... Finalement, le miracle vint et je l'ai dirigé 547 fois. Cette période marqua alors la renaissance de l'opérette viennoise ».

C'est le début d'une longue collaboration entre les deux hommes. Il devient très rapidement le plus brillant chef d'orchestre de l'Age d'Argent de l'opérette viennoise dirigeant les œuvres de ses collègues Oscar Straus, Emmerich Kalman, ... 

Non seulement il continue à répéter, à diriger mais il trouve le temps de composer et dans les années qui suivent, il produit un nombre important d'opérettes et de mélodies: en 1908, « Der grosse Name », en 1909, « Die lustigen Weiber von Wien », en 1910, « Das Glücksmädel » (avec Alexandre Girardi) et en 1911, « Die eiserne Jungfrau » avec Hans Niese. « Servus Du » et « Gavotte Poupée » datent de ces années-là.

En 1913, Robert Stolz innove, une nouvelle fois, en écrivant la première musique de film allemand (film d'Alexandre Girardi « Der Millionenonkel »). Un orchestre joue dans la salle, pendant la séance, une musique spécialement composée sur le sujet, 15 ans donc avant le 1er film sonore.