Der Film spielt im Jahr 1863 zur Zeit des Sezessionskrieges. Die Handlung beginnt in einem Lazarett in der Nähe eines Schlachtfeldes in Tennessee. Dem Nordstaaten-Lieutenant John Dunbar droht verletzungsbedingt eine Beinamputation. Verzweifelt nutzt er einen Moment, in dem er unbeobachtet ist, und reitet auf das Schlachtfeld, um sich erschießen zu lassen. Ungetroffen überlebt er und verhilft – unbeabsichtigt – mit dieser Aktion den Unionisten zugleich zum Sieg, sodass diese Dunbar nach dem Kampf als Helden feiern. Mit der Hilfe des Leibarztes eines beeindruckten Offiziers kann danach sein Bein vor der Amputation bewahrt werden. Das Pferd Cisco wird ihm als Belohnung überlassen.
Dunbar darf sich seinen nächsten Einsatzort aussuchen. Er wählt Fort Sedgwick, ein im Grenz- und Indianerland gelegener Außenposten, um den Westen besser kennenlernen zu können. Major Fambrough, der Dunbars Versetzung unterzeichnet hat, nimmt sich kurz darauf das Leben. Nach tagelanger Reise findet Dunbar das Fort im April des Jahres. Entgegen seiner Erwartung ist es verlassen und verwahrlost. Während er dort auf Soldaten und auf neue Befehle wartet, setzt er den Posten wieder instand. Währenddessen tötet eine Gruppe Pawnee-Indianer den auf der Rückreise vom Fort befindlichen Bauern, mit der Absicht, seinen Skalp als Trophäe zu erlangen.
Auch einen Monat nach seinem Eintreffen im Fort ist Dunbar noch ohne Verbindung zur Außenwelt. Einzig ein Wolf beobachtet ihn gelegentlich. Einige Sioux-Indianer bemerken ebenfalls seine Anwesenheit und versuchen vergeblich, sein Pferd zu stehlen. Dunbar reitet daraufhin in deren Dorf, um ihnen zu versichern, dass er keine Gefahr für sie darstellt. Auf dem Weg findet er eine verletzte weiße Frau in Indianerkleidung, die er in das Dorf bringt. Die Sioux schicken ihn jedoch fort.
Um die Gründe für Dunbars Anwesenheit zu erfahren, begeben sich der Sioux-Medizinmann „Strampelnder Vogel“ und einige Begleiter zum Fort. Durch Geschenke – Dunbar gibt den Sioux etwas Kaffee und Zucker und erhält von ihnen ein Büffelfell – und nachdem Dunbar die Sioux über die Ankunft einer großen Büffelherde informiert hat, wächst das Vertrauen. Die Sioux-Jäger lassen sich durch Dunbar beim Aufspüren der Herde begleiten, entdecken zu ihrer und Dunbars Bestürzung zuvor aber etliche Kadaver von Büffeln, die offensichtlich von weißen Jägern gehäutet wurden. Bei der anschließenden Büffeljagd, die den Sioux zur Sicherung der Nahrungsmittelvorräte dient, unterstützt Dunbar die Sioux auch mit seinem Gewehr.
Nachdem Dunbar vergeblich versucht hat, den ihn verfolgenden Wolf durch ungelenkes Gestikulieren abzuschütteln, verleihen die Sioux Dunbar den Namen „Der mit dem Wolf tanzt“. Dunbar lässt „Strampelnder Vogel“ über dessen Frage, wie viele Weiße noch kommen werden, bewusst im Unklaren. Er erhält im Sioux-Dorf ein eigenes Zelt und verbringt mehr und mehr Zeit bei den Sioux, deren Leben er als sehr harmonisch empfindet. Er lernt die weiße Frau, die „Steht mit einer Faust“ heißt und ihrem Adoptivvater „Strampelnder Vogel“ als Sprachmittlerin zwischen seinem Stamm und Dunbar dient, und die Sprache der Sioux näher kennen. „Steht mit einer Faust“ wuchs bei dem Stamm auf, nachdem sie als Siedler-Kind einem tödlichen Überfall auf ihre Eltern durch Pawnee-Indianern entkam. Aus Verzweiflung über den kürzlichen Tod ihres Ehemanns, eines Sioux, versuchte sie sich das Leben zu nehmen. Der Versuch misslang, führte jedoch zu den Verletzungen, mit denen Dunbar sie auffand.
Während viele der männlichen Sioux des Dorfes zu einem Kampf ausgeritten sind, wird das Sioux-Dorf von Pawnee-Kriegern angegriffen, die den Sioux die Nahrungsmittelvorräte rauben wollen. Da Dunbar die verbliebenen Sioux zuvor mit Schusswaffen aus dem Fort ausgerüstet hat, verteidigt er mit ihnen das Dorf erfolgreich gegen die Angreifer. Von den Sioux daraufhin gefeiert, empfindet er großen Stolz. Mit der Hilfe von „Steht mit einer Faust“, in die er sich verliebt hat und die er den Traditionen der Sioux gemäß heiratet, beherrscht er mittlerweile die Sprache der Sioux. Erst nach der Hochzeit informiert er „Strampelnder Vogel“ darüber, dass wahrscheinlich noch sehr viele Weiße in das Gebiet der Sioux kommen werden.
Als die Sioux in ihr Winterquartier umziehen, reitet Dunbar allein zum Fort Sedgwick zurück, um sein Tagebuch zu holen und damit alle Spuren zu verwischen. Bei seiner Ankunft haben mittlerweile Soldaten der Union Stellung in dem Fort bezogen. Die Soldaten erschießen Dunbars Pferd „Cisco“ und stellen ihn vor die Wahl, entweder mit ihnen zu kooperieren und beim Aufspüren von Indianern und möglichen weißen Gefangenen zu helfen, oder ihn wegen Hochverrats anzuklagen. Der in Indianertracht gekleidete Dunbar weist eine Zusammenarbeit zurück, woraufhin er in Ketten aus dem Fort gebracht wird. Unterwegs schießen Soldaten aus dem Konvoi den Wolf nieder. Bei der Durchquerung einer Furt überfallen die Sioux den Konvoi und helfen Dunbar zu fliehen.
Im Winterlager des Sioux-Stammes angelangt, äußert Dunbar seine Absicht, die Sioux zu verlassen. Damit möchte er weitere Gefahren vom Stamm abwenden, da die Soldaten nach ihm suchen werden. Kurz vor dem Aufbruch Dunbars und seiner Frau erhält er von einem Sioux-Jungen sein Tagebuch zurück, das dieser im Fluss gefunden hat. Während die Soldaten in der Wildnis Spuren der Sioux finden, reiten die beiden weg. Zu Beginn des Abspanns erfährt der Zuschauer, dass Jahre später das freie Leben der Sioux durch das weitere Vordringen der Weißen endete und dass der Wilde Westen Teil der Geschichte wurde.