Michael Blake avait écrit un premier scénario au début des années 80. Lorsque Kevin Costner en eut vent, il suggéra à Blake de plutôt transformer cet écrit en un roman, pour accroitre ses chances d'en faire un film. Le scénariste suivit son conseil, et finit par trouver un éditeur en 1988. Costner acheta immédiatement les droits du livre pour le cinéma, afin de réaliser Danse avec les loups.
En cours de production, il s'est su que le film dépassait son budget initial, forçant Kevin Costner à combler ces pertes de sa poche. Des rumeurs ont alors couru sur Danse avec les loups comme "le film sera un western décevant de plus" ou "encore un western qui coûte les yeux de la tête", ceci en référence à La Porte du paradis, film sorti en 1980, et qui avait plus que dépassé son budget d'origine. Ces rumeurs devinrent même une expression pour désigner le film de Costner comme "La porte de Kevin". Cela n'empêcha pas Danse avec les loups de remporter plusieurs Oscars.
Le précédent western à avoir remporté un Oscar du meilleur film était La Ruée vers l'Ouest avec Richard Dix, sorti en 1931 !
Sept Oscars sont venus récompenser le film lors de la 63e cérémonie de remise des statuettes dorées. Danse avec les loups a remporté l'Oscar du Meilleur montage, de la Meilleure photographie, du Meilleur son, du Meilleur scénario adapté, de la Meilleure musique, du Meilleur réalisateur et du Meilleur film. En revanche, aucun des trois acteurs nommés cette année-là (Kevin Costner, Graham Greene et Mary McDonnell) n'est reparti avec l'Oscar de la catégorie dans laquelle il était pressenti.
Le film fut tourné dans le Dajota du sud, une région de collines rocheuses. Les champs de maïs que l'on aperçoit au début ont été planté spécifiquement pour le film, et les quelques arbres que l'on aperçoit spécialement peints de différents tons de rouges et de bruns, pour représenter l'automne.
Il s'agit de la première réalisation de Kevin Costner.
Deux des bisons domestiques utilisés pour le film ont été prêtés par le chanteur Neil Young.
Dans le film, tous les rôles d'indiens ont été interprétés par de véritables Amérindiens, descendant pour la plupart du peuple Sioux. Ainsi, tous ces acteurs on pu tourner en parlant le Lakota (la langue la plus utilisée par les sioux depuis des siècles), notamment en comptant sur l'aide de Doris Leader Charge (grande représentante du peuple sioux).
Dans le générique, on peut voir dans la partie des remerciements le nom du réalisateur Kevin Reynolds. Celui-ci a en effet aidé Kevin Costner à la réalisation de Danse avec les loups lors de la difficile séquence de la chasse aux buffles. Mais la collaboration professionelle entre les deux hommes ne débute pas là : en 1985, Kevin Reynolds dirige l'acteur débutant dans la comédie Bringue d'enfer, puis après Danse avec les loups, ils se retrouvent sur le tournage de Robin des Bois, prince des voleurs en 1991. Leur dernière collaboration remonte à Waterworld en 1995, tournage pendant lequel les tensions entre les deux hommes ont été nombreuses.
La propre fille de Kevin Costner, Annie, joue dans Danse avec les loups : elle interprète le rôle de "Dressée avec le poing" jeune. Lors de la scène du rêve, la jeune fille, qui pense être poursuivie, se met à s'enfuir et à jeter de brefs coups d'oeil par dessus ses deux épaules, alors que son père lui avait demandé de ne regarder qu'au-delà de son épaule droite. Cette "désobéissance" est surtout due au très jeune âge de la fillette, six ans au moment du tournage, et qui confondait encore à l'époque sa gauche et sa droite.
Le plupart des membres de l'équipe s'étaient donnés des surnoms indiens. Ainsi, le monteur Neil Travis était "Par-dessus les collines" et la scripte "Sable dans les dents", en référence au fait qu'elle était toujours souriante.
Le pape Jean Paul II a déclaré que la musique de John Barry pour ce film était l'un de ses disques préférés.
La scène du troupeau de bisons nécessita plus de 2000 bêtes, et l'utilisation de 9 caméras en simultané.
Lors de la scène où le jeune indien est chargé par un bison, ce dernier charge en réalité sur... des cookies Oréos, son pêché mignon !
Dans la scène d'ouverture, deux docteurs examinent John Dunbar: l'homme sur la table est la doublure de Kevin Costner. Ceux qui jouent les docteurs sont le producteur et le réalisateur du film : Jim Wilson (côté gauche) et Costner lui-même, sur la droite. Les voix ont été doublées par d'autres acteurs.
Kevin Costner avait prévu que le personnage du Major Fambrough soit joué par Marlon Brando, rôle qui échut finalement à Maury Chaykin.
Viggo Mortensen avait été choisi pour jouer le rôle du lieutenant Dunbar. Finalement, il ne joue pas dans le film mais jouera malgré tout le rôle dans The Holy Road (2011), la suite de Danse avec les loups, en développement en 2011.
Le film Danse avec les loups a été tourné en fonction du déroulement réel de l'histoire originale. En effet, à cause du climat et des changements de saisons associés au nombre conséquent de scènes devant se tourner à l'extérieur, Kevin Costner a dû se résoudre à suivre l'ordre chronologique, ce qui est, dans l'industrie cinématographique, un procédé très rare.
Danse avec les loups a rapporté 424 millions de dollars dans le monde lors de sa sortie en salles. Il s'agit de loin du film le plus rentable réalisé par Kevin Costner puisque Postman a été un gros échec commercial (20 millions de dollars de recettes pour un budget de 80 millions...) et Open Range en avait récolté 69 (pour un budget de 26 millions). Danse avec les loups se classe par ailleurs en deuxième position des films les plus lucratifs dans lesquels a joué Kevin Costner, derrière Batman v Superman : L’Aube de la Justice et ses 868 millions de dollars de recettes et Man of Steel et ses 668 millions.
Dans le but de mener à bien cet ambitieux projet qu'a été Danse avec les loups, Kevin Costner a refusé plusieurs rôles convoités. Parmi eux, nous pouvons compter celui de Jack Ryan dans À la poursuite d'Octobre Rouge (joué finalement par Alec Baldwin) réalisé par John McTiernan et sorti en 1990. L'acteur jouera toutefois dans The Ryan Initiative en 2014 avec Chris Pine dans le rôle-titre.
Il était également question que Viggo Mortensen campe le personnage du lieutenant Dunbar et Marlon Brando celui du Major Fambrough, mais finalement les choses ne se sont pas faites.