Die Geschichte spielt während des Krimkrieges, in einem russischen Lager bei Isaktscha, am westlichen Ufer des Donaudeltas, gegenüber einer türkischen Festung, die am anderen Donauufer liegt. Es ist strenger Winter, die Donau zugefroren. Beim morgendlichen Appell begrüßen die Kadetten ihren Sergeanten mit einer Schneeballschlacht. Nur der Leutnant Wladimir muss noch (mit einem Marschlied) geweckt werden und beschwert sich, dass man seinen schönen erotischen Traum gestört hat. Ein Marketender kommt ins Lager, verkauft Wodka und erfährt so ganz nebenbei etwas über die Mannschaftsstärke der Russen. Statt diesem wird aber dann kurz darauf ein Anderer als angeblicher Spion aufgegriffen. Wladimir erkennt in ihm jedoch Julian von Golz, einen deutschen Journalisten und Kriegsberichterstatter, auch kurz nur Reporter genannt. Dieser erklärt dann den staunenden Umstehenden, was ein Reporter eigentlich ist: "Ein Reporter ist ein Mann, dem man nichts verbergen kann".

Die Soldaten langweilen sich in dem Lager, die Feinde stehen sich unbeweglich gegenüber, es ist nichts los. Wladimir muss ein pikantes Erlebnis erzählen. Als Tscherkessin Fatinitza verkleidet hatte er einst eine verheiratete Dame besucht und in dieser Verkleidung mit deren Schwager, einem hohen Offizier, eine weitere Eroberung gemacht. Nur mit Mühe konnte er dessen Nachstellungen entkommen. Es war derselbe Offizier, dessen Nichte Lydia Wladimir später umworben hatte und weswegen er dann, um ihn von der Nichte fernzuhalten, hierher strafversetzt wurde. Julian kommt auf die Idee, im Kampf gegen die Langeweile ein Theaterstück aufzuführen. Mangels Frauen soll sich Wladimir wieder als solche verkleiden. Alle, bis auf den Sergeanten verschwinden, um sich für die erste Probe vorzubereiten.

Da kommt unangemeldet der General Kantschukoff zur Inspektion in das Lager. Er hat's gern mit der Knute und will fuchsteufelswild alle und jeden wegen der unkriegerischen Zustände im Lager bestrafen. Als er jedoch den als Frau verkleideten Wladimir entdeckt, schmilzt er dahin. Er ist der Offizier, der sich damals unsterblich in Fatinitza verliebt hatte, und Wladimir/Fatinitza kann ihn jetzt um den Finger wickeln. Der General schenkt "ihr" sogar einen Ring und betrachtet sich fortan als mit "ihr" verlobt. Kaum ist die eine peinliche Situation ausgestanden, kündigt sich schon die nächste an. Die Nichte Lydia fährt mit einem Schlittengespann vor "Welche Lust beim Spiel der Flocken leicht dahin zu gleiten". Sie will angeblich bei den Heldentaten ihres Onkels dabei sein, in Wirklichkeit ist sie ihrem strafversetzten Verehrer nachgefahren. Da Lydia die Ähnlichkeit Fatinitzas mit Wladmir sofort auffallen muss, gibt sich Wladimir auf Anraten Julians als Schwester seines angeblich gefangen genommen Ichs aus. Kantschukoff muss nun seine Nichte irgendwo sicher unterbringen. Als einziges festes Gebäude bietet sich ein nahes Kloster an, in welchem sie zusammen mit Fatinitza die Nacht verbringen soll. Julian ist neidisch: "Er ruht da drinnen warm mit ihr und ich bleib' draußen hier und frier'", gleichzeitig wittert er aber eine amouröse Geschichte. Zu dieser kommt es aber nicht, weil gleich darauf die Türken die Donau überqueren und die beiden Frauen für den Harem des Izzet Pascha rauben. Julian lassen sie unbehelligt, der soll die Lösegeldforderung an die Russen überbringen. Jetzt plant Julian gar einen sensationellen Artikel in 12 Folgen.

Im Harem des Izzet Pascha machen die Haremsdamen gerade Toilette, um "den Gebieter zu entzücken". Sie reagieren empört, als ihnen ihr Gebieter weiteren Zuwachs für den Harem ankündigt, dazu auch noch Christinnen. Als Reformtürke, wie er sich immer bezeichne, wolle er doch die Vielweiberei abschaffen. Tut er doch auch - immer nur eine pro Nacht. "Reformen tun Not bei der türkischen Nation". Als die beiden Gefangenen, Lydia und Wladimir hereingebracht werden, erklärt er sofort Lydia zu seiner Lieblingsfrau.

Auf Geheiß Izzet Paschas muss sich Lydia haremsmäßig umkleiden, Fatinitza soll ihr dabei helfen. Es entsteht diesmal sogar eine hochnotpeinliche Situation, bei der Wladimir/Fatinitza vor Aufregung so die Hände zittern, dass er sich sowohl beim Frisieren als auch beim Schmuck anlegen für Lydia völlig ungeschickt anstellt. Als er ihr jetzt auch noch beim Umziehen behilflich sein soll, ist es genug. Er gesteht Lydia, zunächst noch im Auftrag seines angeblichen Bruders, dessen Liebe zu ihr um dann ganz am Schluss doch noch zuzugeben, dass dieser "Bruder" er selbst ist. Lydia verzeiht ihm seine Maskerade, lässt ihn hoffen, aber verspricht ihm noch nicht zu viel.

Die Haremsdamen stürmen herein und wollen die beiden Konkurrentinnen töten. Wladimir kann sie durch das Angebot einer hohen Geldsumme dazu überreden, ihnen bei der Flucht behilflich zu sein. Als er den Haremsdamen gar seine wahre Identität preisgeben will, wollen sie ihm nicht glauben, dass er ein Mann sei, so perfekt ist seine Verkleidung. Letztendlich bietet er den Beweis durch einen Kuss an, hier schreitet aber Lydia eifersüchtig ein, ein weiterer Beweis ihrer Zuneigung.

Julian von Golz erscheint als Parlamentär, um die Auslösebedingungen für die beiden Gefangenen auszuhandeln. Zuvor kann er noch mit Wladimir Kontakt aufnehmen und dessen Flucht vorbereiten. Sein Begleiter, der Sergeant, kann Wladimir sogar dessen Uniform heimlich zustecken. Der Pascha will nur über Fatinitza verhandeln, Lydia will er unbedingt behalten. Ansonsten ist er dem Reporter gegenüber so aufgeschlossen, dass er ihm, sich als Reformtürke über den Koran hinwegsetzend, und um des eigenen Ruhmes willen, sogar seinen Harem zeigt. Dabei erklärt er dem Reporter, wie und wodurch er welche Haremsdame erwerben konnte und lässt zu guter Letzt sogar zu, dass die Damen sich entschleiern. Julian ist entzückt.

Der Pascha lädt die Gesandtschaft zum abendlichen Karagois, einem archaischen türkischen Schattenspiel ein. Als dessen Handlung den hochdramatischen Höhepunkt erreicht hat, brechen, nicht wie im Spiel angekündigt, zwei wilde Tiere aus dem Gebüsch hervor sondern die Russen, angeführt vom General Kantschukoff von hinten durch die Leinwand. Die Festung ist mit Hilfe der Haremsdamen gestürmt, aber zum Leidwesen des Generals ist Fatinitza nicht aufzufinden. Julian gibt vor, sie sei entführt worden. Zur Strafe nimmt der General dem Pascha seine Haremsdamen weg, die sich darüber auch noch freuen. Dem Pascha bleibt nur die Knute des Generals. Kismet!

Im Palais des Generals Kantschukoff in Odessa. Glockenklänge künden vom Frieden, jedoch Lydia sorgt sich um den verschollenen Wladimir. Ein Gast, der sich ankündet, ist leider nicht der Vermisste, sondern nur dessen Freund Julian. Er bringt jedoch die frohe Botschaft, dass Wladimir am Leben und ganz in der Nähe sei. Von Lydia erfährt er, dass sie von ihrem Onkel mit dem alten Fürsten Swertikoff verheiratet werden soll. Als er auf den General trifft, erklärt ihm dieser den Grund, warum er es so eilig hat, Lydia zu verheiraten. Er selbst hatte 100.000 Silberrubel auf das Auffinden von Fatinitza ausgesetzt - nun habe sie der bulgarische Spion (der Marketender aus dem 1. Akt) tatsächlich gefunden und heute noch solle sie sein werden. Der General lässt Julian einen Brief von diesem Schurken vorlesen, in welchem minutiös beschrieben wird, durch wie viele Hände Fatinitza seit ihrer Entführung gegangen und dass sie trotzdem immer noch unversehrt sei. Der General kann dazu nur noch stammeln: "Fatintiza, Fatintiza, Fatintiza, was hast du alles durchgemacht." Heute aber noch soll Fatinitza mit einem Schiff aus Konstantinopel hier eintreffen, und daher muss Lydia an seinen alten Freund, der ihm einmal das Leben gerettet hatte, verheiratet werden, damit sie aus dem Hause ist, denn zwei Frauen im Haus geht nicht gut!

Endlich kommt Wladimir und trifft zunächst nur mit Julian und Lydia zusammen. Unter Zeitdruck durch Julian können sich die zwei Verliebten nochmals gegenseitig ihrer Liebe versichern. Während dieser Versicherung wird auch ein Marschlied gesungen, das mit einem anderen Text versehen Weltberühmtheit erlangt hat. Danach trifft Wladimir erstmals als Mann auf den General. Nach anfänglicher Irritation wegen der Ähnlichkeit mit Fatinitza bietet der General dem Leutnant eine Adjudantenstelle bei ihm an, befördert ihn zum Major und bittet ihn förmlich um die Hand seiner Schwester. Souffliert vom Reporter teilt ihm Wladimir mit, Fatinitza sei schon verlobt, er selbst habe einem befreundeten Leutnant sein Ehrenwort gegeben. Jetzt kann er, immer assistiert von Julian, einen Deal aushandeln. Sein Jawort gegen das Jawort des Generals für Lydia. Der General gibt nach und drängt jetzt sogar darauf, dass die Hochzeit Lydias mit Wladimir sofort stattfinden muss, bevor noch Fatinitza eintrifft.

Während der Trauung erweist sich die inzwischen eingetroffene und von dem Gauner vorgeführte Fatinitza als dunkelhäutige Afrikanerin gleichen Namens. Julian löst die Geschichte dahingehend, dass er den bulgarischen Spion als Betrüger entlarvt und einen Brief der "echten" Fatinitza vorliest, in welchem diese dem General mitteilt, sie sei aus unerfüllter Liebe zu ihm aus dem Leben geschieden, sie gebe hiermit ihren Verlobungsring zurück (den sich Julian zuvor von Wladimir hat geben lassen), ihr letztes Wort vor dem Tod sei "Kantschukoff" gewesen. Der untröstliche General ist von diesen letzten Worten tief gerührt. Als Wladimir von der Trauung zurückkehrt und Julian fragt, was er denn nun mit Fatinitza gemacht habe, antwortet der: "Hab sie einfach umgebracht". Nach dieser, für Wladimir und Lydia glücklichen Wende schließt der bärbeißige General die Neuvermählten an sein Herz zum "Happy Ende".

Fatinitza war bis zum ersten Weltkrieg noch eine der erfolgreichsten Operetten. Mit etwa zwölfhundert Aufführungen allein auf deutschsprachigen Bühnen lag das Werk an Aufführungszahlen zwischen der Schönen Helena und dem Mikado. Doch eine der herausragenden Eigentümlichkeit dieser Operette, die Hosenrolle für eine Sängerin, die einen Mann spielt, der wiederum eine Frau spielt, ließ sie in neuerer Zeit völlig in Vergessenheit geraten, da Hosenrollen zumindest in der Operette aus der Mode kamen. Was man seit 1911 dem Rosenkavalier bis heute noch zubilligt, wollte man für die Operette nicht mehr akzeptieren. Dabei zeichnet sich Fatinitza neben dieser Besonderheit auch noch durch eine hinreißende Musik von außerordentlicher Qualität aus. Wie bei Suppé üblich, hat auch Fatinitza wieder einige opernhafte Züge, vor allem in den Ensembles und im großen Duett, die aber durch in der Volkstheater-Tradition stehenden Couplets, einige Walzerklänge und Märsche aufgelockert werden.

Hier eine Auswahl besonders prägnanter Musiktitel: Die wuchtig endende Introduktion malt ein Stimmungsbild der Winterlandschaft und führt das russische Kolorit in die Operette ein. Das Traumlied des Wladimir wird durch einen mitreißenden Marsch eingeleitet und endet nach lyrischem Mittelteil mit leicht resignierendem Unterton im Walzertakt. Das humorvolle, in atemlosen Sechzehntel-Takt vorgetragene Reporterlied bringt schon damals auf den Punkt, was man auch heute der schreibenden Zunft noch anlasten kann. Temperamtvoll ist die Schlittenarie, mit langer instrumentaler Einleitung, romantischem Mittelteil und anspruchsvollen Koloraturen am Schluss. Und wiederum vorzugsweise wuchtig präsentiert sich das kriegslärmende Finale I mit einer Entführungsszene.

Der reizvolle Toilette-Chor vierer Haremsdamen und vier Sklavinnen, welcher den 2. Akt eröffnet, besticht durch sein orientalisches Klangbild in Verbindung der hohen Frauenstimmen. Ganz im italienischen Opernstil, auch entsprechend ausführlich, erklingt das "Enthüllungs"-Duett der beiden Frauen, in welcher die eine gesteht, dass sie ein Mann ist und in der Schlusspartie hören wir eine Phrase, der wir, leicht verändert, im "Dompfaff-Duett" des Zigeunerbaron wieder begegnen. Das daran anschließende Sextett "Ha ein Mann" erinnert an Offenbach'sche Rundgesänge und wird von manchen gar, zumindest was Takt und Struktur betrifft, als Orpheus-Zitat angesehen. Als besonderes Juwel kann ein weiteres Sextett "Silberglöckchen klingen helle" bewertet werden, das auch durch eine außerordentlich ungewöhnliche Harmonik auffällt.

Die Glockenarie, die sowohl den Frieden als auch den dritten Akt einläutet, ist eine wunderschöne Romanze, die mit echten Glockenklängen von der Bühne aus begleitet wird. Darauf folgt eines der witzigsten Duettinos der ganzen Operette, bei welchem ein haarsträubend erlogener Brief vom Reporter Julian so herzergreifend vorgetragen wird, dass dem entsetzten General nur noch das stakkatohafte Stammeln des Namens "Fatinitza" und ein kurzer Ausdruck des Bedauerns zu singen bleibt. Ein von der Struktur her ebenfalls recht opernhaftes Terzett "Dich wiederzusehen" beginnt, bedingt durch die Wiedersehensfreude, zunächst noch im schnellen 4/4 Takt, verlangsamt sich dann, dramatisierend zu einer Schlachtschilderung zum 2/4 Takt, um den nachfolgenden Marsch einzuleiten. Dieser Marsch "Vorwärts mit frischem Mut" ist zum Hauptschlager der Operette geworden und wurde gar nach der Berliner Erstaufführung am 16. September 1876 zum Gassenhauer, der, vom Volksmund mit eigenem Text versehen, auch heute noch so gesungen wird:

"Du bist verrückt mein Kind, 

du musst nach Berlin. 

Wo die Verrückten sind 

da gehörst du hin."

Bevor dieser Marsch im Schlussgesang des Finales noch einmal erklingt, setzt der Chor mit "russischer Folklore" noch ein paar klangliche Farbtupfer in die Operette.