אתרי הצילומים שנבחנו היו מקסיקו, קנדה ושבע מדינות נוספות, ולבסוף נבחרה דקוטה הדרומית. הסיבות לכך היו עדרי הסוסים והביזונים במדינה, והקהילות האינדיאניות הרבות, שאנשיהן יוכלו לשמש ניצבים. עדר הביזונים שצולם לסרט היה בבעלותו של ל. רוי האוק, ומנה מעל 3,000 ביזונים. בעקבות המעבר לדקוטה הדרומית, שונה גם השבט האינדיאני העומד במרכז העלילה: בעוד בספר תיאר הסיפור שבט קומאנצ'י במערב טקסס, מציג הסרט שבט לקוטה, סעיף של שבט הסו. מרכז ההפקה הוקם בעיר רפיד סיטי.
בלייק קרא עדויות רבות בגוף ראשון לפני שכתב את התסריט כדי להשיג אמינות, והושפע במיוחד מביוגרפיה של מנהיג הסו סוס משוגע, שהיה לדבריו "אחד מהאנשים הגדולים ביותר שאי פעם חיו בעולם הזה". מספר דמויות נוצרו בהשראת אנשים אמיתיים, בהם מייג'ור פמברו, שהתאבד ביריית אקדח בראשית הסרט. הדגם לדמותו של "ציפור בועטת" הוא מנהיג שבט הקיווה בשנות ה-70 של המאה ה-19 בעל השם הזהה, "ציפור בועטת" . חייה של הדמות "עומדת עם אגרוף" מבוססים על הביוגרפיה של סינתיה אן פרקר , שנכלאה בילדותה בידי שבט קומאנצ'י, נישאה בהמשך למנהיג השבט, והייתה אמה של קוואנה פרקר . מיסיונר אמריקאי בשם ג'ון דנבאר הפיץ את הנצרות בין הפאוני בראשית המאה ה-19, אך בלייק טוען שדמותו של גיבור הסרט אינה מבוססת על אדם היסטורי מסוים, והיא ניסיון להעברת החיים האינדיאניים לצופים.
המורה האינדיאנית דוריס לידר צ'ארג' העניקה לשחקנים שמדברים בסרט בשפת הלקוטה שיעור מזורז בן שלושה שבועות בשפה לפני תחילת הצילומים. ביחד עם אלברט וייט האט תרגמה את התסריט ללקוטה. וייט האט ולידר צ'ארג' פישטו את שפתם של הדיאלוגים שתרגמו כדי להקל על השחקנים, והסירו את הסימנים המציינים דיבור נשי וגברי. לכן השתמשו חלק מהשחקנים האינדיאנים הגברים, וגם קוסטנר, בצורת דיבור נשית. גם במהלך הצילומים ליוותה לידר צ'ארג' את הדיבור בלקוטה, ובמהרה הציעו לה קוסטנר והמלהקת אליזבת ליוסטיג תפקיד שכולל דיבור – אשתו של הצ'יף "עשרה דובים".
ביצירת כ-200 התלבושות לסרט הושם דגש רב על הדיוק ההיסטורי. אחת מהמומחיות המרכזיות ללבוש אינדיאני, ילידת הגבעות השחורות קאת'י סמית', הכינה עבור מעצבת התלבושות אלזה זמפרלי לבוש אינדיאני בטכניקות מסורתיות. ספריהם ואיוריהם של אירופים, שביקרו שבטי אינדיאנים במאה ה-19 וציירו אותם, הדריכו את יוצרי התלבושות בעת עיצובן של התלבושות האינדיאניות. ליצירת התלבושות השתמשו המעצבים בעורותיהם של 625 איילים, כמויות גדולות של עורות ופרוות ביזונים, וכן נוצות, חרוזים ותכשיטים מקוריים. משום שנשרים הם עופות בסכנת הכחדה, השתמשו השחקנים האינדיאנים רק בנוצות שהועברו בירושה. גם הטקסים האינדיאנים לוו בלימוד הנושא מראש, וסייוורט יאנג בר (Cyvert Young Bear), חבר להקת מוזיקת הלקוטה המסורתית Porcupine Singers, הציג לכוריאוגרפים של הסרט ריקודי ביזונים וקרקוף מסורתיים.
המעצב האמנותי שיצר את התפאורה לסרט היה ג'פרי ביקרופט. חלק גדול מהרקוויזיטים, בהם קשתות וכלי נשק אחרים, רסנים לסוסים, כלי בית ואמצעי בישול אינדיאניים, ואוהלי טיפי, הוכנו בידי מומחים ממכון סמית'סוניאן, תוך שימוש בחומרי גלם טבעיים, כמו חלקי גוף שונים של ביזונים. המודל לציורים שעל הסוסים היו ציורי קיר עתיקים מאוהלי טיפי. בין הסימנים שצוירו – יד, המסמלת לוחם שמתאבל על מת. השקעה נוספת בתפאורה נעשתה בהעברת משרדו של מייג'ור פמברו בשלמותו מלוס אנג'לס לדקוטה הדרומית עבור הצילומים.
ליהוק.
את תפקידי האינדיאנים שיחקו רק שחקנים ממוצא אינדיאני, כדי לשמור על האותנטיות של הסרט. מלבד אלפי מבחני בד לשחקנים הראשיים, שכר צוות הסרט את שירותיהם של כמאה וחמישים אנשים משבט סו משמורת האינדיאנים רוזבאד ששימשו ניצבים, ובסך הכל נשכרו 250 ילידים אמריקאיים לשחק בסרט. מרבית השחקנים האינדיאניים שמשחקם בסרט כולל גם דיבור אינם שייכים לשבטי סו; כך למשל, גרהאם גרין הוא משבט אוניידה ; טנטו קרדינל , שמשחקת את "צעיף שחור" (אשתו של "ציפור בועטת"), משתייכת לקבוצות הקרי והמייטי ; ורודני גרנט – הוא "רוח בשערו" – הוא ממוצא אומהי .
הגורם המכריע לליהוקה של מרי מקדונל – אז שחקנית תיאטרון בניו יורק – לתפקיד "עומדת עם אגרוף" היה העובדה שלא הייתה מוכרת בעולם הקולנוע, והעובדה שפניה היו חרוצות קמטים, כפי שרצה קוסטנר.
שלב הצילומים.
שלב הצילומים, שעל פי דיווחים אמור היה להתבצע במקסיקו החל ממרץ 1989, התאחר ל-17 ביולי, וצולם בעשרים ושבעה מוקדים בדקוטה הדרומית.
תיאורי הקרבות שפותחים את הסרט מתרחשים בסתיו במדינת הדרום טנסי, אבל בגלל בעיות לוגיסטיות לא ניתן היה לצלם אותם לא במקום המדויק ולא בעונה הנכונה. כדי להעניק לעלוות העצים ולשאר הצמחים בשדות מראה שמתאים לעונת השנה המתוארת, השתמשו אנשי התפאורה בכמעט 40,000 ליטרים של צבע. כדי לצלם את הסצנה השתמשו גם ב-250 שחקנים חובבים, שמשתתפים באופן קבוע בשחזורים של מלחמת האזרחים האמריקאית.
הביזונים מהחווה של ל. רוי האוק הופיעו בכמה וכמה סצנות, שצילומן ארך שמונה ימים. צלמי הסרט נעזרו בצילומי הביזונים בהליקופטר, בעשר מסחריות, ב-24 אינדיאנים על סוסים ללא אוכף ובעשרים בוקרים. בסרט מופיעים שני ביזונים מאולפים ומבויתים – אחד בבעלות המוזיקאי הקנדי ניל יאנג – ואחד שהיה הקמע של חברת בשר מדקוטה הדרומית. הביזונים שמוטלים מתים בסרט הם פיתיונות עשויים תיל ופרווה.
סצנה שמופיעה בגרסה הארוכה יותר של הסרט, שבה רוכב דנבאר לצד "ציפור בועטת" באזור מיוער שהושחת לחלוטין בידי ציידים לבנים, צולמה בפארק הלאומי גרנד טיטון בוויומינג, ומחנה החורף של הסו צולם בקניון ספירפיש בקרבת רפיד סיטי.
על פי הודעה לעיתונות, צילם הבמאי האמריקאי קווין ריינולדס חלקים מן הסרט ב"יחידה שנייה". היו שמועות כי ריינולדס הצטרף לצוות הסרט כדי להקל על קוסטנר, שהיה עמוס מדי. עם זאת, לדברי עורך הסרט ניל טרוויס, ריינולדס לא ביים את השחקנים ולא דיאלוגים, וקוסטנר היה אחראי לעיצוב כל סצינות "היחידה השנייה" שצילם ריינולדס.
הצילומים הסתיימו בין 21 ל-23 בנובמבר 1989. על פי דיווחים שונים, עלה משך זמן הצילומים על לוח הזמנים המתוכנן ב-23 עד 30 יום, ונעשה שימוש בכ-1.8 מיליון דולר יותר מאשר התקציב הראשוני. הסרט כונה גם "שערי קווין" (Kevin’s Gate), ברמיזה לתהליך הייצור הכושל של המערבון "שערי החופש" (Heaven’s Gate) משנת 1981. כדי להנמיך עלויות, בצוות הצילום וההפקה היו גם עובדים שלא היו חברי איגודים. עם זאת, גם חברי האיגוד הבינלאומי International Alliance of Theatrical Stage Employees היו מעורבים בתהליך היצירה, בהם עורך הסרט טרוויס והצלם דין סמלר .
גמר-הפקה.
כדי לגייס כסף לפוסט-פרודקשן, תהליך שאורכו היה כחודשיים, נמכרו אביזרים ותלבושות ששימשו ליצירת הסרט.
קוסטנר אמר בראיון בשנת 2011 שבסצנה אחת בלבד השתמשו באפקטים מיוחדים: משום שביזונים הם יצורים חסרי מנוחה והם התקשו למנוע מהם לזוז, השתמשו יוצרי הסרט באנימטרוניקה כדי לייצר אשליה של עדר שלם במצב סטטי.
המלחין הבריטי ג'ון בארי, שיצר בעבר את המוזיקה למספר סרטי ג'יימס בונד, הלחין את הפסקול של הסרט, וגם ניצח על הקלטותיו; הוא עשה זאת בסיועו של הזמר-יוצר ג'ון קוינמן (John Coinman), שעזר להפוך את המוזיקה והריקודים של הלקוטה לאותנטיים ככל האפשר. כדי להגיע למטרה זו האזין בארי לפני ההקלטה למוזיקה מסורתית של הלקוטה.
יציאה לאור.
בהקרנות מוקדמות של הסרט, שהתקיימו החל ממאי 1990, בין השאר בסיאטל ובפיניקס, הוצגה גרסה קצרה בעשר דקות מהגרסה שיצאה לבסוף לאקרנים. קמפיין השיווק של החברה המפיצה, אוריון, כלל גם פרסום ברדיו בשפת הלקוטה, ששודר בתחנות רדיו אינדיאניות, וכן קידום צולב בשיתוף ערוץ דיסקברי. בנוסף, במספר תחנות טלוויזיה הוצג עד סוף 1990 הסרט התיעודי "The Making of Dances with Wolves" (יצירת "רוקד עם זאבים").
הקרנת הבכורה העולמית התקיימה ב-19 באוקטובר 1990 בוושינגטון די. סי. הקרנות הסרט בארצות הברית החלו ב-9 בנובמבר 1990, רק בתשע ערים מרכזיות. עם תחילת ההקרנות בפריסה ארצית, ב-21 בנובמבר, הועלה הסרט ב-750 בתי קולנוע לפחות. במדינות אירופה החלו להציג את הסרט בפברואר 1991, ובישראל הוא הוצג החל מ-22 או 23 במרץ 1991. הקרנת הבכורה המדינתית האחרונה המתועדת ב-IMDb התקיימה בצ'כוסלובקיה בתחילת יוני 1991.
גרסה מורחבת.
מלבד הגרסה שאורכה שלוש שעות, והיא זו שהוצגה בבתי הקולנוע בתחילה, פרסמה החברה המפיצה גרסה ארוכה יותר (בכ-50 דקות), שאורכה כמעט ארבע שעות. גרסה זו נוצרה במקור להצגה מחוץ לארצות הברית. היא מכילה קטעים שיוצרי הסרט נאלצו לחתוך בשלב העריכה של הגרסה המקורית, וחלק מהסצנות מוצגות בה בסדר שונה. הגרסה הוצגה לראשונה בלונדון ב-20 בדצמבר 1992, ובהמשך היא הוקרנה במקומות אחרים באירופה, בהם בגרמניה. הצגות הבכורה של הגרסה הארוכה בארצות הברית היו ב-7 וב-10 בנובמבר 1993, כאשר רשת הטלוויזיה ABC הציגה את הגרסה בתור מיני-סדרה במסגרת תוכניות הערב שלה. היא לא הוצגה בבתי הקולנוע בארצות הברית.
הסצנות שנוספות בגרסה המדוברת הן סצנה שבה רוכבים דנבאר ו"ציפור בועטת" דרך יער שהשחיתו לחלוטין ציידים לבנים; ציידים לבנים טובחים בביזון, מה שמשפיע על החלטתו של דנבאר לחזור לחברה הלבנה; ומספר סצנות נוספות של "עומדת עם אגרוף" ודנבאר, שמדגישות את הפערים התרבותיים בין השניים.
פסקול.