Am 07. Juli 1990 feierte „Winnetous letzter Kampf” Premiere am Kalkberg. Passenderweise hatte die DDR bereits rund zwei Wochen zuvor ihren letzten Kampf gefochten und verloren. Das lange so Unvorstellbare vollzog sich: Europa rückte zusammen. Die deutsche Einheit war nur ein Vorspiel einer beispiellosen Kontinent übergreifenden Entwicklung. Große Hoffnungen begleiteten diese Zeit des Wandels. Inmitten dieses Klimas sollten auch die Karl-May-Spiele nicht von Veränderungen verschont bleiben.
Das Jahrzehnt begann mit den letzten beiden Bühnenjahren des legendären Film-Winnetous Pierre Brice. Wenn gleich die von ihm mitgestalteten Inszenierungen wie eine Selbstbeweihräucherung wirkten, so zog er doch die Massen an. Selbst das eher beschauliche, langweilige und durch die wahllose Montage von Filmszenen aufgeführte Stück „Winnetou – Das Vermächtnis“ tat dem Erfolg keinen Abbruch. 317.395 Zuschauer besuchten 1991 die letzte Saison des Franzosen in Bad Segeberg. Diese Marke sollte für lange Zeit als uneinholbar gelten. Als sich Brice, allem Werben der Kalkberg GmbH zum Trotz, nicht auf einen erneuten Vertragsabschluss einließ, begann die Suche nach einem neuen Winnetou-Darsteller. Doch hatte man sich an die üppigen Besucherzahlen zu sehr gewöhnt!?
Fakt ist, dass nicht ein junger aufstrebender Mime das Zepter übernahm, sondern ein nicht weniger Kamera erfahrener Schauspieler. Einer der nur einige Jahre jünger war als sein Vorgänger: Gojko Mitic. Der ehemalige Nebendarsteller mehrerer Karl May Filme war in der gerade untergegangenen DDR der vielleicht einzige Schauspieler mit Star-Qualität gewesen. Durch die jahrzehntelange Verkörperung von historischen Häuptlingsfiguren (mit deutlich politisch geprägter Botschaft) hatte er einen hohen Bekanntheitsgrad im ganzen ehemaligen Ostblock gewonnen. Mitic nahm die Aufgabe dankend an. Niemand konnte zu diesem Zeitpunkt ahnen, dass er nun über anderthalb Jahrzehnte hinweg den Häuptling der Apachen am Kalkberg verkörpern würde. Die Hoffnung, den nach Brice‘ Abschied erwarteten Schwund an Besuchern durch neue ehemalige DDR-Bürger und Mitic-Fans kompensieren zu können, erfüllte sich indes nur teilweise. Bereits in der Erstsaison sank die Besucherzahl quasi auf das Niveau der Prä-Brice-Zeiten. Für die Segeberger Verantwortlichen immer noch ausreichend und angesichts der schnell wachsenden Popularität von Mitic auch diesem nicht angelastet. Soviel Kontinuität man in der Wahl des Hauptdarstellers bewies, so abenteuerlich stellte man sich in allen anderen Bereichen dar. Die Spiele suchten ihre Identität.
Mitte der Neunziger schien die Kreativität von Regisseur Serge Nicolaescú erschöpft. Ein neuer Mann musste her. Die Buchautoren wechselten stätig. Im Ergebnis durfte sich der Besucher auf 
abwechslungsreiche aber nicht immer qualitativ gute Umsetzungen der Mayschen Stoffe freuen. Nachdem die Spiele der magischen 200.000-Besucher-Grenze 1994 erschreckend nah gekommen waren. Die Aufführung des bekanntesten May-Buches, „Der Schatz im Silbersee“, schien keine Erfolgsgarantie zu geben. Die Kalkberg GmbH wagte einen größeren Umbruch.
Die Verpflichtung von Thomas-Louis Pröve ließ aufsteigende Zahlen erhoffen. War er doch mit der Arena, aus seiner Zeit als Assistent von Klaus-Hagen Latwesen, bestens vertraut. Mit viel Elan und Einsatzfreude widmete sich dieser der Aufführung „Winnetou I”. Mit rund 230.000 Zuschauern fuhr er ein mehr als respektables Ergebnis ein – und musste gehen. Pröve selbst war hier wohl dynamischer als es manchem Entscheidungsträger gefiel. Seine geforderten Veränderungen stießen nicht bei allen auf Zustimmung. So feierte Norbert Schultze jr. im Folgesommer seinen Einstand als Regisseur bei den Karl-May-Spielen. In zwei aufeinander folgenden Spielzeiten konnte er die Spiele festigen.
1999 erfolgte dann jedoch überraschend erneut eine Kehrtwende. Pierre Brice kehrte zurück. Dieses Mal als Regisseur. An diese Saison erinnern sich viele mit Grauen: Brandkatastrophe, Textbuch-Katastrophe, Inszenierungs-Katastrophe – und das bei einem selten gut besetzen Ensemble. In mancherlei Hinsicht wurden damals die Weichen für den Erfolg der Zukunft gestellt. Personen wurden an die Bühne gebunden, die langjährige Publikumslieblinge und Erfolgsgaranten vor und hinter den Kulissen sein sollten.
Der Abschluss der Saison 1999 bedeutete auch das Ende der Ära von Ernst Reher, dem Geschäftsführer der Kalkberg GmbH. Unter seiner Nachfolgerin sollten die Karl-May-Spiele eine ganz neue Dynamik gewinnen.
Übersicht der Spielzeiten:
1990 – Winnetous letzter Kampf
1991 – Winnetou – Das Vermächtnis
1994 – Der Schatz im Silbersee
1997 – Winnetou und Old Firehand