En 1863, le lieutenant nordiste John Dunbar, qui doit subir une amputation de la jambe à la suite d'une grave blessure durant la guerre de Sécession, remet sa botte, choisit au hasard un cheval nommé Cisco et réagit de manière désespérée et suicidaire en effectuant un aller-retour au galop devant les lignes ennemies ; il échappe miraculeusement aux balles, ce qui encourage ses compagnons à lancer une attaque décisive, et lui permettra par la suite de bénéficier des soins du chirurgien personnel du général, admiratif de son exploit.
Une fois décoré et entièrement rétabli, il demande sa mutation dans un avant-poste de l’Ouest sauvage pour échapper à l'horreur du souvenir de la guerre. Il se retrouve seul et satisfait de l'être, dans un « fort » – en réalité une cabane en bois avec une remise séparée – mystérieusement déserté par la petite troupe qui était censée le tenir, et attend l’arrivée de renforts hypothétiques. Il a pour compagnons un jeune loup solitaire qu'il appelle « Chaussettes » (« Two Socks ») et qu'il apprivoise lentement, ainsi que sa fidèle monture Cisco. Mais les renforts n'arrivent pas car les deux seuls hommes qui connaissent la présence de Dunbar dans ce poste avancé meurent avant de pouvoir la signaler : le major déséquilibré qui l'y a affecté se suicide juste après le départ de Dunbar et le muletier qui l'y a conduit avec le chargement de vivres, de matériel et de munitions destiné à la garnison est massacré sur la route du retour par un petit groupe d'Indiens pawnees.
Ses journées se résument à parcourir la région puis à consigner, dans son journal, ses observations. Seulement, une tribu indienne de Sioux installée à proximité découvre son poste. Les relations qu'il entretient avec quelques-uns des membres de la tribu, dont on découvre qu'elle est installée à quelques heures de chevauchée du poste de Dunbar, sont conflictuelles, faites de méfiance et de peur réciproques, marquées par plusieurs tentatives des Sioux de voler son cheval. Progressivement, Dunbar établit le contact en sauvant une Indienne blanche, Dressée avec le Poing (Stands with the fist), qui tentait de se suicider après la mort de son époux sioux. La communication est difficile, et les échanges brefs. Mais le lieutenant va finir par se lier d'amitié avec la tribu, à tel point qu'il est invité régulièrement au campement indien. Un jour, alors que ses amis sioux attendent fébrilement l'arrivée des bisons, il se précipite jusqu'à leur campement pour leur annoncer qu'il les a repérés, passant près du poste qu'il tient. Il est invité à les chasser avec eux. Durant la chasse, il sauve un jeune Indien (Sourit Beaucoup) de la charge d'un énorme bison, ce qui lui vaut le respect et l'admiration de toute la communauté, ainsi que sa totale admission parmi eux. Le lieutenant est aperçu en train de jouer avec le loup Chaussettes qu'il a « adopté » ; les Indiens le surnomment alors Danse avec les Loups (Dances with wolves).
Il tisse et entretient des rapports privilégiés avec Oiseau bondissant, le « saint homme » de la tribu, père adoptif de Dressée avec le poing, avec Cheveux au vent, un grand guerrier, ou encore Dix Ours, le chef du village. Il tombe sous le charme de Dressée avec le poing qui sert d'intermédiaire entre lui et les Indiens, car elle parle anglais, sa langue natale, puisqu'elle a été recueillie et adoptée très jeune par les Sioux car elle est la seule à avoir survécu et échappé au massacre de sa famille par les Pawnees, la tribu ennemie.
Au fil des mois, le lieutenant John Dunbar délaisse totalement son rôle de soldat, et devient sioux. Il se marie avec Dressée avec le poing après qu'Oiseau bondissant a levé son deuil, puis sauve toute la tribu d'une attaque des Pawnees, en allant récupérer sous la pluie avec Sourit beaucoup le stock de fusils qu'il avait enterré près du fort.
Mais les soldats blancs arrivent dans les territoires des Indiens ; cette menace – qui pèse sur tout le film – inquiète la tribu. Celle-ci décide de migrer pour l'hiver et le lieutenant retourne une dernière fois au fort, pour récupérer le carnet dans lequel il tient son précieux journal depuis le premier jour, de manière à ne pas laisser d'indice.
Lorsqu'il parvient près du poste, il découvre que la relève est enfin arrivée, faite de soudards et d'illettrés brutaux qui symbolisent le retour à la civilisation qu'il avait quittée. Le poste s'est agrandi avec des tentes de campement et de nombreux soldats le gardent. Vêtu et paré en Indien, le lieutenant se fait tirer dessus et son cheval est mortellement touché, lui-même étant brutalement frappé.
Par la suite, il est renvoyé vers l'est enchaîné et sous bonne escorte, afin d'y être jugé et pendu pour trahison. Pendant ce transfert, ses gardes tuent Chaussettes qui s'était montré pour suivre son ami. Mais les Indiens, inquiets de ne pas voir revenir Danse avec les Loups, ont envoyé des guerriers à sa recherche. Ils lancent l'assaut sur le convoi et délivrent le lieutenant, massacrant son escorte, lui-même tuant le plus ignoble et le plus veule de ses gardiens, celui qui avait dérobé son journal et l'utilisait comme papier hygiénique.
Après avoir rejoint le campement d'hiver récemment installé, John Dunbar décide de quitter la tribu en compagnie de sa femme Dressée avec le Poing, après avoir persuadé Dix Ours de déplacer le campement. En effet, l'armée le considère comme un traître et sa recherche risque de mettre en péril la communauté. Il décide alors de partir pour pouvoir s'expliquer, muni, à titre de preuve, de son précieux journal restitué par Sourit Beaucoup qui l'avait miraculeusement récupéré flottant dans la rivière après l'assaut sur le convoi. L'armée trouve le campement déménagé et un loup hurle dans le lointain.
Dixième western majeur avec un héros qui quitte la civilisation blanche pour vivre parmi les Indiens. Danse avec les loups (1990) succède ainsi à La flèche brisée (Delmer Daves, 1950), Au-delà du Missouri (William Wellman, 1951), La rivière de nos amours (André de Toth, 1955), Le jugement des flèches (Samuel Fuller, 1957), Un homme nommé cheval (Elliot Silverstein, 1970) et Le soldat bleu (Ralph Nelson, 1970), Little Big Man (Arthur Penn, 1970), Jeremiah Johnson (Sydney Pollack, 1971). Il faudra ensuite attendre de nouveau 25 ans pour voir The revenant (Alexandro Gonzalez Inarritu, 2015).
En 1990, Danse avec les loups rafle sept Oscars, dont ceux du meilleur film et du meilleur réalisateur. Kevin Costner, qui en a bavé pour monter le film, savoure sa victoire. A cette époque, il est à l’apogée de sa carrière. Les spectateurs découvrent en salles un spectacle flamboyant de trois heures où les sentiments se mêlent à la beauté des espaces américains. Un western qui prêche, sans niaiserie apparente, la tolérance envers les Indiens représente un exploit assez rare en soi. Plus de dix ans après, Fox Pathé Europa propose en DVD la version longue du film. Cinquante minutes de film réintégrées qui ralentissent considérablement la narration de l’épopée de John Dunbar.