Pendant les deux années qu'il va passer à Paris, il compose « La montagne bleue » sur un livret d'Albert Willemetz qui doit être créée au Châtelet et collabore à la version française de « Balalaïka » au théâtre Mogador. Il retrouve quelques uns de ses amis et fait la connaissance d'Yvonne Louise Ulrich, surnommée « Einzi » (de einzig signifiant unique) pour son dévouement auprès des réfugiés. Grâce à elle, il réussit, dans un premier temps, à sortir du camp d'internement du stade de Colombes, puis à partir aux USA. Au début de l'été 40, Hitler et ses troupes occupent Paris. L'espoir des émigrés s'effondre.

Ayant refusé de rentrer en Allemagne, sur invitation personnelle du Ministre de la propagande, le Dr Goebbels, ses mélodies, ses œuvres sont interdites et son nom est supprimé des génériques des films dont il a composé la musique. A l'heure actuelle, le nom de Robert Stolz n'a toujours pas retrouvé sa place dans de nombreux génériques, plus de 50 ans après.

Arrivé à New-York, on lui propose un contrat de 300 $ pour écrire une suite symphonique. Un journal se souvient de lui:

« C'est lui qui écrivit "Two Hearts in three quarter time". Cela fait plaisir de se rappeler ces bonnes vieilles valses viennoises ».

Les firmes cinématographiques se souviennent également du compositeur et, après avoir obtenu quelques engagements pour des court-métrages, il obtient un contrat pour composer la musique de « Spring Parade ». Le film, avec Deanna Durbin dans le rôle principal, est un immense succès aux Etats-Unis. Le 11 Janvier 1941, Robert Stolz est « nominé » pour les Oscar dans la catégorie « meilleure mélodie ».

De nombreux orchestres, dont le New-York Philharmonic Orchestra, l'invitent. New-York sert de plaque tournante pour ses bonds vers les différents états des USA et d'Amérique du Sud. On le surnomme « Ambassadeur de la musique viennoise ». La musique des Strauss, Millöcker, Lehar et ... Stolz composent ses programmes.

En 1942, une tournée de concerts est organisée, complétant les représentations d'opérettes. On y retrouve les plus belles mélodies de Johann Strauss, Oscar Straus, Franz Lehar, Emrich Kalman et de Robert Stolz. La première a lieu au Lewison Stadium devant 20 000 auditeurs.

Robert Stolz va présenter ce spectacle intitulé « A night in Vienna » à travers les Etats-Unis. Un journal, « The Etude », écrit en avril 1942:

« Robert Stolz est le Roi de la valse viennoise ressuscitée, le Roi des compositeurs d'opérettes. Il est le Johann Strauss d'aujourd'hui ».

Quel plus beau compliment pouvait-il recevoir ? Lui qui a décidé de consacrer sa vie et sa carrière à la défense, à la promotion de la musique qu'il aime : la musique viennoise !

Au cours de cette tournée, à Princeton, dans l'Etat du New-Jersey, il est reçu, avec Einzi, par Albert Einstein. Lors de cette rencontre, Robert Stolz a la surprise de voir le physicien prendre son violon. Et que joue-t-il devant ses invités ? : « Im Prater blühn wieder die Baüme », « Du sollst der Kaiser meiner Seele sein », ... ainsi que des mélodies de Kreisler. Au cours de la discussion qui s'en suit, Robert Stolz est appelé « Roi de la mélodie » par son hôte illustre.

Toujours en 1942, il donne, comme chef d'orchestre au Cosmopolitan Opera de New-York, des représentations de la « Chauve-Souris », du « Baron Tzigane » et de « L'étudiant pauvre ». D'autres seront données à Boston, Philadelphie, Baltimore, Cleveland, Chicago, Detroit, San Francisco, Los Angeles et Hollywood.

En 1943, au New-York Majestic Theater, il présente au public une nouvelle « Veuve Joyeuse » (arrangement signé Robert Stolz) avec Jan Kiepura et Martha Eggerth.

Entre ses diverses tournées, il trouve le temps de composer. Il travaille sur la musique du film de René Clair, « C'est arrivé demain » avec Dick Powell et Linda Darnell dans les rôles principaux et monte à Broadway sa comédie musicale « Mister Strauss goes to Boston ». La chorégraphie est de George Balanchine.

Malgré les succès et les triomphes aux USA, Robert Stolz ne peut oublier sa patrie. Ses pensées vont toujours à Vienne, à sa ville natale Graz mais également à Paris. De nouvelles œuvres révèlent son état d'esprit: « Nostalgia », « God bless my homeland », « Tears of Vienna ». « Paris rêveries », la suite « Mes amours » sont composées en souvenir de son passage  dans la capitale française comme son opus 714, « Souvenirs of Paris ». Sa tristesse est accentuée par la réception d'un avis: « Dénaturalisation de l'aryen Robert Stolz et confiscation de tous ses biens  » en date du 28 mars 1942.

 Robert Stolz s'expliquera, à la radio, sur les raisons de son départ d'Autriche :

« ... autrefois, quand j'ai quitté mon pays aux sons barbares du pas de l'oie, j'ai tout de suite pensé que nous n'étions pas faits pour cela. C'est comme si on avait affublé la tête de Mozart d'un casque, accroché un sabre à la taille de Schubert et entouré de barbelés le cou de Johann Strauss en leur disant ensuite: "Garde à vous ! Composez quelque chose de beau maintenant.". En somme, une idée affreuse et c'est ainsi que j'ai noué ma besace et que je suis parti ... ».

En 1944, il est à nouveau « nominé » pour les Oscar pour la musique du film de René Clair.

Avec la fin du second conflit mondial, les derniers jours de l'exil approchent pour Mr et Mme Stolz. (Robert Stolz a épousé, en juin 1946, Yvonne Louise Ulrich à Reno dans le Nevada. Einzi devient la 5ème épouse du compositeur).

A l'automne 46, Robert et Einzi prennent le premier avion en partance pour Vienne. Ils ont obtenu les visas n° 1 et 2. Aux journalistes qui lui demandent les raisons de son départ des USA où il a su conquérir le public et accumuler les succès en 5 ans, il répond :

« Je voudrais revoir l'Eglise des Frères Mineurs sous la neige. Cela vaut bien quelques sacrifices et privations ».

Quelques années plus tard, ce retour sera commenté par le Dr Marcel Prawy, chef dramaturge de l'Opéra de Vienne:

« Qu'un homme aussi célèbre et aussi fêté à l'étranger rentre, de son plein gré, dans son pays, était pour les Autrichiens, dans ces années qui suivirent la seconde guerre mondiale, d'une grande portée morale.

De même que sa célèbre marche militaire avait, jadis, accompagné les soldats de l'Empereur, une nouvelle marche saluait maintenant les Nations-Unies ».