I april 1863 henvendte digteren Henrik Hertz sig til Heise for at foreslå ham at komponere musik til et syngestykke til Det Kongelige Teater. Heise gik straks i gang med musikken til Hertz’ tekst om magtkampe og intriger i en by i Tyrkiet og kærligheden mellem en simpel men modig lastdrager og pashaens (embedsmandens) smukke og fornemme datter.
I begyndelsen gik arbejdet stærkt. Den 7. april 1863 sendte Hertz teksten til Paschaens Datter til Heise, der allerede 5. maj kunne meddele, ”at jeg er færdig med første Act, det vil sige alle Sangpartierne med en Bas til Antydning af Orchestret”. Hertz og Heise forestillede sig, at stykket kunne opføres i teaterets kommende eller måske næstfølgende sæson og havde konkrete rolleindehavere i tankerne under arbejdet.
Men så begyndte det at trække ud. Frederik den 7. døde i november. Juleaften gik tyskerne ind i hertugdømmerne Lauenburg og Holsten, og troppeopbuddet øgedes i løbet af januar 1864. Det forstyrrede Heises arbejde med syngestykket. ”At den tunge Stemning, som Begivenhederne have fremkaldt, ikke har kunnet virke animerende paa kunstnerisk Frembringelse, er vel naturligt”, skrev han til Hertz. Og det hele blev ikke bedre af nederlaget ved Dybbøl, hvor Heises kone, Ville, mistede en bror.
Hertz var utålmodig og rykkede Heise for at få at vide, hvor langt musikken var kommet. En opførelse af syngestykket rykkede dog ikke nærmere af, at Heise endelig blev færdig.
Paschaens Datter var Heises første erfaring med Det Kongelige Teater. En negativ erfaring i den forstand, at teateret hele tiden udskød opførelsen af stykket. I februar 1869 skrev Heise i et brev, at ”jeg i Fremtiden betragter det kongelige Theater som en for mig lukket Anstalt”. 30. september samme år blev Paschaens Datter dog endelig opført.
Publikum mødte talstærkt op, og der var positive anmeldelser.
I Leipzig mente Signale für die musikalische Welt, at ouverturen var det mindst overbevisende, men at Heise uden tvivl var ”den mest talentfulde af de yngre skandinaviske komponister”. Og hjemme i Danmark fremhævede Berlingske Tidende blandt andet Heises lyriske talent. Fædrelandet mente, at ”Hr. Heise er Herre over Formen i en ualmindelig Grad” og skrev blandt andet også: ”Musiken er saa livlig og tillige saa indtagende smuk i mange Numre, helt igjennem saa dannet i Aand og Form, endelig saa letfattelig, at alle Tilhørere have Meget at nyde. Den er derhos saa omfangsrig, at selv de mere øvede Tilhørere langtfra kunne faa Alting med den første Gang...”
Fem af sangene udkom særskilt (for sang og klaver) i 1869.
Litteratur, cd-indspilninger og trykte udgaver
