Năm 1863, Trung úy John J. Dunbar bị thương trong trận chiến tại Chiến trường St. David ở Tennessee. Bác sĩ phẫu thuật định cắt cụt chi của Dunbar; tuy nhiên, thay vào đó anh chọn chết nơi sa trường, lấy ngựa cưỡi đi dọc theo chiến tuyến của quân miền Nam. Quân miền Nam liên tục nã đạn vào anh và bắn trượt, còn Quân đội miền Bắc tận dụng sự mất tập trung của địch để tiến hành cuộc tấn công thành công. Dunbar nhận được lời tán dương vì lòng dũng cảm và sự chăm sóc y tế giúp anh giữ được chân của mình. Sau đó, anh được tặng Cisco (con ngựa chở anh trong lần đi quyết tử) và để anh lựa chọn nơi đóng quân. Dunbar đề nghị chuyển đến biên giới phía tây, để anh có thể nhìn thấy nó trước khi nó biến mất.
Dunbar được chuyển đến Công sự Hays, một pháo đài lớn do Thiếu tá Fambrough chỉ huy (ông này tỏ ý coi thường sự nhiệt tình của Dunbar). Ông đồng ý đưa Dunbar đến tiền đồn xa nhất thuộc quyền tài phán của mình là Công sự Sedgwick và nâng ly trước khi chia tay Dunbar. Dunbar không hề hay biết là Fambrough (bị bệnh tâm thần nặng và tùy tiện ra lệnh mà ghi lại trong hồ sơ lưu giữ) đã tự sát gần như ngay lập tức sau khi Dunbar rời đi. Dunbar đi cùng Timmons, một người chở lượng thực bằng xe kéo la. Họ tới nơi và thấy công sự bị bỏ hoang. Bất chấp mối đe dọa từ các bộ lạc bản địa gần đó, Dunbar quyết định ở lại và tự mình quản lý đồn.
Anh bắt đầu tái xây dựng và tái tích trữ công sự, ưa thích chốn tích mịch này, ghi chép nhiều quan sát của mình vào nhật ký. Timmons bị Pawnee sát hại trên chuyến đi trở về Công sự Hays. Cái chết của cả Timmons lẫn Fambrough làm quân đội không hay biết về nhiệm vụ của Dunbar, và không có viện binh nào khác đến tiếp ứng.
Dunbar tiếp xúc những người hàng xóm thuộc tộc Sioux khi họ định trộm ngựa của anh và buông lời đe dọa. Vì quyết định rằng việc trở thành mục tiêu là một viễn cảnh tồi tệ, anh đi tìm trại của người Sioux và cố gắng bắt chuyện. Trên đường đi, anh bắt gặp Stands with a Fist. Sau khi bị bắt từ gia đình da trắng của mình, cô được nhận làm con nuôi và đồng hóa thành con gái của Kicking Bird, thầy thuốc của bộ tộc. Cô đang tự cắt mình theo nghi thức để thương tiếc người chồng Sioux quá cố. Dunbar đưa cô trở lại Sioux để dưỡng thương. Mặc dù ban đầu bộ lạc có thái độ thù địch, song một số thành viên sớm bắt đầu tôn trọng anh.
Dunbar dần thiết lập mối quan hệ với Kicking Bird, chiến binh Wind in His Hair và cậu thanh niên Smiles a Lot, họ ban đầu đến thăm trại của nhau. Rào cản ngôn ngữ làm họ thất vọng và Stands with a Fist làm người phiên dịch, mặc dù gặp khó khăn. Cô chỉ nhớ một chút tiếng Anh từ thời thơ ấu của mình trước khi những người còn lại trong gia đình cô bị giết trong một cuộc đột kích của người Pawnee.
Dunbar phát hiện ra rằng những câu chuyện anh từng nghe về bộ lạc là không đúng sự thật, và anh ngày càng tôn trọng và đánh giá cao lối sống và văn hóa của họ. Nhờ học ngôn ngữ của họ, anh được người Sioux chấp nhận làm vị khách danh dự sau khi anh kể cho họ nghe về một đàn trâu di cư và tham gia vào cuộc đi săn. Khi ở Công sự Sedgwick, Dunbar kết bạn với một con sói mà anh đặt tên là "Two Socks" vì đôi chân trước màu trắng của nó. Nhờ quan sát thấy Dunbar và Two Socks rượt đuổi nhau, người Sioux đặt cho anh cái tên "Dances with Wolves". Trong thời gian này, Dunbar cũng tạo dựng quan hệ tình cảm với Stands with a Fist và cung cấp vũ trang cho bộ lạc để giúp họ bảo vệ ngôi làng khỏi cuộc tấn công của bộ tộc đối thủ Pawnee. Cuối cùng Dunbar giành được sự chấp thuận của Kicking Bird để kết hôn với Stands with a Fist và bỏ Công sự Sedgwick.
Vì mối đe dọa ngày càng leo thang từ người Pawnee và Hoa Kỳ, tộc trưởng Ten Bears quyết định chuyển bộ lạc đến trại đông của mình. Dunbar quyết định đi cùng họ, nhưng thấy trước hết phải lấy nhật ký của mình từ Công sự Sedgwick, vì anh nhận ra rằng nó sẽ cung cấp cho quân đội phương tiện để tìm ra bộ tộc. Khi đến nơi, anh thấy công sự đã bị Quân đội Hoa Kỳ chiếm đóng. Vì mặc bộ quần áo của tộc Sioux, những người lính đã nổ súng, lấy mạng Cisco và bắt giữ Dunbar, bắt anh vì tội phản bội.
Hai sĩ quan thẩm vấn anh, song Dunbar không thể chứng minh câu chuyện của mình vì một hạ sĩ tìm thấy cuốn nhật ký của anh và lấy nó làm giấy vệ sinh. Sau khi từ chối làm thông dịch viên với các bộ lạc, Dunbar bị buộc tội đào ngũ và thuyên chuyển trở lại phía đông như một tù nhân. Những người lính của đội hộ tống đã bắn Two Socks khi con sói định đi theo chân Dunbar, bất chấp Dunbar đã cố can thiệp.
Chung cuộc, tộc Sioux theo dõi đoàn xe, tiêu diệt đám lính và giải thoát cho Dunbar. Họ khẳng định rằng họ không xem anh là một người da trắng, mà là một chiến binh của Sioux có tên Dances with Wolves. Tại trại mùa đông, Dunbar quyết định rời đi với Stands with a Fist vì sự hiện diện thường trự của anh sẽ gây nguy hiểm cho bộ tộc. Khi họ rời đi, Smiles a Lot trả lại cuốn nhật ký mà anh đã tìm thấy trong lúc giải cứu Dunbar, còn Wind in His Hair hét lên với Dunbar, nhắc anh rằng anh ta là bạn của Dunbar, trái ngược với lần gặp gỡ đầu tiên của họ khi anh ta hét vào mặt Dunbar một cách thù địch.
Quân đội Hoa Kỳ thì tìm kiếm trên núi, song không thể xác định được vị trí của Dunbar hoặc bộ lạc, trong khi một con sói đơn độc hú lên từ xa.
Phần kết viết: "13 năm sau—nhà cửa của họ bị phá hủy, đàn trâu của họ biến mất—nhóm người Sioux tự do cuối cùng quy phục chính quyền da trắng tại Công sự Robinson, Nebraska. Nền văn hóa ngựa vĩ đại của vùng đồng bằng đã biến mất, và biên giới nước Mỹ sẽ sớm đi vào lịch sử."
