Robert STOLZ naît le 25 Août 1880 à Graz, dernier des 12 enfants de Jacob et Ida Stolz. Compositeur, son père, élève de Sechter et de Bruckner, est le directeur du conservatoire de musique de Graz. Il est également un célèbre chef d'orchestre : c'est lui qui dirige la Première de Tannhaüser de Richard Wagner à Vienne.

Ida Stolz est une pianiste très connue. Elle abandonnera rapidement sa carrière de concertiste pour s'occuper de l'éducation de ses enfants. Quant à Thérèse Stolz, tante du jeune Robert, elle est une grande amie de Giuseppe Verdi et l'interprète favorite de ses grands opéras.

Parmi les familiers de la famille Stolz, Anton Bruckner et Johannes Brahms :

« Tous les dimanches, Johannes Brahms venait chez nous. Il avait cette grande barbe dont de vieilles photos donnent une idée. Après le déjeuner, il s'asseyait au piano, avec un gros cigare aux lèvres, et nous jouait ses œuvres ou des valses de Johann Strauss dont il était très friand ».

C'est donc dans une atmosphère musicale que fut élevé Robert. Son talent de compositeur fut découvert très tôt par sa mère. Robert Stolz racontera plus tard:

 « Je dois tout à ma mère. En plus de tout l'amour dont elle m'a comblé, elle a éveillé en moi l'amour de la musique et m'a donné mes premières leçons de piano. Ce faisant, elle a découvert très tôt mon talent de compositeur et m'a enseigné à exprimer en musique tout ce que je ressentais ».

A 7 ans, il donne son premier récital de piano et Johannes Brahms, présent dans la salle, lui augure un brillant avenir.

Les parents Stolz décident alors de confier la formation de leur fils à Engelbert Humperdinck, compositeur de « Hansel und Gretel » et maître de l'opéra féerique.

Neuf ans plus tard, Robert Stolz passe brillamment son examen d'Etat de musique au conservatoire de Vienne. Son opus n°1, « Albumblatt », est dédié le 12 septembre 1895 à son « cher et honoré professeur ». L'année suivante, il est engagé comme co-répétiteur d'opéra à Graz. Il travaille tout le répertoire classique avec l'orchestre, les solistes et les chœurs. A 18 ans, il obtient son premier poste de chef d'orchestre à Marburg (aujourd'hui Maribor).

En 1899, Robert se rend, porteur d'une lettre de son père pour Johann Strauss, à une représentation de la « Chauve-souris » à l'Opéra Impérial de Vienne. Johann Strauss y dirige l'ouverture. Ce sera sa dernière apparition publique. Quelques jours plus tard, il rend visite au Roi de la Valse, et directeur des bals de la cour, à son domicile de l'Igelgasse - brusque révélation de sa voie future de chef d'orchestre:

« J'ai pu ensuite revoir Johann Strauss dans son hôtel particulier de l'Igelgasse. Une inoubliable et noble figure, des mains fines vibrant comme sous l'effet d'une perpétuelle et inaudible musique. Bonté, « conciliance » et modestie étaient tout son être. Un musicien au seuil de l'immortalité à qui, quelques semaines plus tard, plus de 100 000 personnes rendaient les derniers honneurs au cimetière central de Vienne. Après cette représentation de la Chauve-Souris et cette rencontre avec le génie de la Valse, m'apparut la vérité du dicton qui veut qu'il n'y ait pas de musique sérieuse et une musique légère, mais seulement de la bonne et de la mauvaise musique ».

 Il abandonne progressivement les œuvres classiques pour se consacrer à la musique viennoise et straussienne.

« Je me suis dit qu'il y avait assez de chefs pour jouer le répertoire classique et je me suis entièrement consacré à ce musique que j'aime par dessus tout ».

Dés 1899, il écrit sa première pièce chantée, « Studentenulke ».

En 1902, il crée sa seconde opérette, « Schön Lorchen », alors qu'il est chef d'orchestre au théâtre municipal de Salzbourg.

1903 le voit effectuer, en tant que chef d'orchestre, une tournée de représentation d'opérettes viennoises à travers la Russie de Nicolas II, puis chef d'orchestre dans un cirque à Berlin avant d'être engagé au théâtre allemand de Brno.