W następnym, 1890 roku, Lehár, wygrał konkurs na kapelmistrza 25. regimentu piechoty, stacjonującego w położonym niedaleko Wiednia Losonczu. Okres pracy w Losonczu przyniósł, oprócz kilku przelotnych romansów17-letnia córka dowódcy pułku baronówna Vilma Fries zażądała, by Lehár uczył ją śpiewu. Ponieważ młodzieniec nie miał doświadczenia w pedagogicznego, uczył ją tak długo, aż zachrypła. Przerażony, że córka dowódcy straci głos, udał chorobę, a pod jego nieobecność Vilma straciła zapał do śpiewu ()., pierwszą dużą kompozycję Lehára. Wiosną 1891 roku Lehár uczestniczył w Wiedniu w koncercie Johanna Straussa i został wydelegowany wspólnie z kolegą do wręczenia mistrzowi olbrzymiego wieńca laurowego. Pod wrażeniem tego spotkania postanowił stworzyć operę. Pierwsze libretto zatytułowane Kirasjer napisał dla niego zawiadowca miejscowej stacji kolejowej. Kiedy ułożenie do niego muzyki okazało się niemożliwe, napisania kolejnego podjął się przyjaciel z pułku Rudolf Mlčoch. Historia o zbóju imieniem Rodrygo, który porywa piękną Donnę Angelę, pozwala jej jednak pożegnać się z narzeczonym, a ten dusi zhańbioną ukochaną, która umierając, wyznaje mu miłość, została przez Lehára wysłana na konkurs ogłoszony przez księcia saksońsko-kobursko-gotajskiego Ernesta II.