1893 wurde Leutwein in die Kolonie Deutsch-Südwestafrika (das heutige Namibia) versetzt, wo er bereits zwei Jahre später zum Kommandeur der Kaiserlichen Schutztruppe aufstieg. Er befehligte Feldzüge und "Strafexpeditionen" gegen die Völker der Witbooi, Nama und Herero. Seine Niederschlagung der Aufstände der lokalen Bevölkerung wurde offenbar in Berlin als Erfolg angesehen und so wurde Leutwein 1898 schließlich zum Gouverneur der Kolonie Deutsch-Südwestafrika ernannt. Unter ihm begann die systematische Errichtung der deutschen Herrschaft nach dem Prinzip des "teile und herrsche". Statt die direkte Konfrontation mit der einheimischen Bevölkerung zu suchen, versuchte er sich verstärkt darin, die verschiedenen lokalen Gruppen gegeneinander auszuspielen. Zentral war für ihn hierbei, wie er betonte, "nur eine einzige Richtschnur, nämlich diejenige, die am sichersten zu dem erstrebten guten Geschäft führt". Allerdings wurde Leutwein zu Beginn des Herero-Krieges 1904 als Befehlshaber der Schutztruppe von General Lothar von Trotha abgelöst. Stand Leutwein noch für ein Mindestmaß an Mäßigung und für einen ansatzweisen Ausgleich mit der kolonialisierten Bevölkerung (zu den Bedingungen der Kolonisatoren), befehligte von Trotha den Genozid an den Herero und Nama und galt als Vertreter einer Politik des kolonialen Terrors. Nicht zuletzt, weil er die offene Vernichtungspolitik Trothas ablehnte, ließ Leutwein sich in den Ruhestand versetzen.
Vor allem angesichts des Vorgehens seines Nachfolgers wurde Leutwein häufig als der "rationale" und gegenüber der lokalen Bevölkerung gegenüber "human" eingestellte Kolonialist dargestellt. In der Realität heiligte jedoch auch für Gouverneur Leutwein der Zweck die Mittel kolonialer Ausbeutung, welche den systematischen Ausbau der deutschen Herrschaft über das Land, die Errichtung einer weißen deutschen Siedlerkolonie bei Unterwerfung der lokalen Bevölkerung und die Ausbeutung der Bodenschätze zum Ziel hatte. Dies wird auch aus dem folgenden Zitat aus Leutweins Erinnerungen deutlich:
"Mein Streben ging seitdem dahin, die einheimischen Stämme selbst in den Dienst unserer Sache zu stellen, um sie dann gegeneinander auszuspielen. Auch ein Gegner dieser Politik wird mir zugeben müssen, daß es schwieriger, aber auch verdienstvoller war, die Eingeborenen zu bewegen, für uns sich gegenseitig totzuschießen, als vom alten Vaterlande Ströme von Blut und Ströme von Geld zu deren Unterdrückung zu verlangen."
Die historische Forschung ist sich mittlerweile einig, dass Leutwein eine Mitverantwortung für den Genozid durch den deutschen Kolonialismus trug, auch wenn er zu Beginn des Krieges gegen die Herero und Nama abgelöst wurde. Einen wesentlichen Anteil hatte er vor allem am Aufbau des Systems des deutschen Kolonialismus in Südwest-Afrika.
Text: Dr. Hanno Balz, Historiker, in Abstimmung mit der Landeszentrale für politische Bildung und dem Senator für Kultur