1866 beschloß die Regierung, alles daranzusetzen, um den Bozeman Trail rechtzeitig zum Sommeranfang zu öffnen. Da mit einer großen Siedlerwelle zu den Minen in Montana gerechnet wurde, schickte die Armee Colonel Henry B. Carrington und ein Bataillon von siebenhundert Offizieren und Soldaten der 18. Infanterie in das Land am Powder River, wo sie eine Reihe von Forts errichten sollten. Gleichzeitig reiste eine Regierungskommission nach Fort Laramie in der Absicht, die Sioux mit Geschenken und anderen Bestechungsmitteln friedlich dazu zu bewegen, die Weißen durch ihr Bisonland ziehen zu lassen.
Als die Abgesandten in Fort Laramie eintrafen, wurden sie von Oglala, Sicangu und einigen Cheyenne und Arapaho mitsamt ihren Führern bereits erwartet; die Indianer waren durch Läufer herbeigerufen worden. Freudig stellten die Weißen fest, daß zu der Indianerabordnung auch die Sicangu-Häuptlinge Sinte Galeshka (Spotted Trail) und Swift Bear und die Oglala-Anführer Red Cloud und Man Afraid of His Horse gehörten. Diese vier zählten zu den einflußreichsten und mächtigsten Sioux-Häuptlingen.
Den Indianern war nicht bekannt, worüber die weißen Männer reden wollten; sie wußten nur, daß sie mit anderen Stämmen Frieden geschlossen und ihnen dafür üppige Geschenke und andere Bezahlungen gemacht hatten und daß sie nun den Gruppen im Land am Powder River die gleiche Möglichkeit bieten wollten. Die Jagdsaison war wenig erfolgreich verlaufen, und viele Indianerfamilien litten Hunger und Not. Mit Ausnahme von Gruppen wie derjenigen des jungen Oglala-Kriegshäuptlings Crazy Horse, den Miniconjou und Sitting Bulls Hunkpapa, die jede Verhandlung mit den Amerikanern strikt ablehnten, waren die meisten Indianer voller Erwartungen zu diesem Treffen nach Fort Laramie angereist.
Zu Beginn der Konferenz am 5. Juni sagten die Regierungsbeauftragten, sie seien an friedlichen Beziehungen zu den Indianern interessiert und wollten nur das Recht, einige Straßen durch ihr Gebiet zu legen und zu benützen, "wie es für die öffentlichen Dienste notwendig ist, und damit Siedler zu den Bergbaugegenden im Westen gelangen können". Den Indianern war klar, daß die Weißen vom Bozeman Trail sprachen; offenbar hatten sie geahnt, daß dies der Hauptgrund für die Versammlung sein würde, und wirkten deswegen nicht überrascht. Doch aus Angst, die Häuptlinge könnten die Konferenz abbrechen, machten die Beauftragten utopische Versprechen, von denen die Indianer wußten, daß sie nie eingehalten werden könnten, etwa, daß die Reisenden auf dem Bozeman Trail sich nur an die Straße halten würden und ihnen nicht gestattet sein würde, "das Wild in der Region, die sie durchquerten, zu stören."
Die Indianer wollten den Vorschalg und die versprochene Bezahlung überdenken und baten um eine Verschiebung der Konferenz. am 13. Juni trafen sich die Unterhändler erneut, doch die Versammlung wurde sofort aufgelöst durch die Ankunft von Colonel Carrington und seine Truppen, die auf dem Weg ins Land um den Powder River im Fort Station machten. Als Carrington erklärte, er habe den Befehl, zum Schutz des Bozeman Trail eine Kette von Forts zu errichten, wurden die Indianer wütend, insbesondere Red Cloud.
Der Oglala-Kriegshäuptling war mit seinen rund 45 Jahren eine imposante Erscheinung; seine langen, schwarzen Haare waren in der Mitte gescheitelt und fielen ihm auf die Schultern. Durch seine zahlreichen Angriffe gegen die Pawnee, die Crow und andere Feinde der Sioux war er weithin bekannt und galt als ein angesehener Krieger. Darüber hinaus war er aber auch ein ehrgeiziger und gerissener Politiker, und obwohl er kein ziviler Häuptling war, genoß er bei den Oglala denselben, wenn nicht größeren Einfluß als ihr Häuptling Man Afraid of His Horse.
Als ihm das hinterhältige Vorgehen der Regierungsbeamten klar wurde, warf er ihnen vor:

"Der Große Vater schickt uns Geschenke und verlangt neue Straßen.
  Aber der weiße Häuptling stiehlt mit seinen Soldaten die Straße,
  bevor die Indianer ja oder nein sagen!"

"Die weißen Männer haben die Indianer Jahr um Jahr zurückgedrängt, so daß
  wir gezwungen sind, in einem kleinen Gebiet nördlich des Platte zu leben,
  und jetzt soll uns unser letztes Jagdgebiet, die Heimat des Volkes, genommen
  werden. Unsere Frauen und Kinder werden verhungern, aber was mich betrifft,
  so sterbe ich lieber im Kampf als an Hunger."

Im Sommer errichtete Carrington drei Forts entlang dem Bozeman Trail; sein Hauptquartier war das mittlere, Fort Phil Kearny, das südlich in der mit Kiefern bewachsenen Hügellandschaft des heutigen Sheridan, Wyoming, lag. Crazy Horse und andere Krieger bedrängten die Bauarbeiter, und als die Sonnentänze im Sommer vorüber waren, setzten sie die Angriffe auf den Trail vermehrt fort. Sie griffen Emigranten, Planwagenzüge und Boten an, überfielen Forts selbst, stahlen Vieh und töteten Soldaten, die sich aus dem Schutz der Forts hervorgewagt hatten. Im Oktober galt die Verbindung als so gefährlich wie eh und je, und Carringtons einsame Festungen waren im Belagerungszustand.
Als im Dezember die Herbstjagd zu Ende ging, begann Red Cloud seinen Krieg. Sein Ziel war, die Soldaten aus dem Land zu vertreiben. In einem Lager in der Nähe von Fort Phil Kearny versammelten sich über eintausend Indianerfamilien. Der erste Versuch, Soldaten in einen Hinterhalt zwischen den Hügeln zu locken, scheiterte, als die Truppen eine Gruppe von Sioux-Lockvögeln nicht verfolgen wollten. Doch Carringtons Offiziere fühlten sich in dem belagerten Fort gefangen und verlangten ungeduldig, offensiv gegen die Indianer vorzugehen. "Mit achtzig Leuten könnte ich durch das gesamte Gebiet der Sioux reiten", prahlte Captain William J. Fetterman, der im November mit einer Kavallerie-Einheit zur Verstärkung Carringtons eingetroffen war. Die große Chance des arroganten Fetterman kam am 21. Dezember, als er - zufällig mit genau achtzig Männern - ausgeschickt wurde, um eine Gruppe von Holzfällern zu befreien, die von den Sioux gefangengenommen worden war. Unüberlegt führte Fetterman seine Leute geradewegs in einen Hinterhalt. Hunderte von Sioux überfielen ihn und töteten ihn mit allen seinen Soldaten.
Diese Niederlage entsetzte die Regierung und verstärkte den Einfluß der Friedensbefürworter. Doch das Militär war noch nicht bereit, sich geschlagen zu geben. "Wir müssen mit ernsthaften Vergeltungsmaßnahmen gegen die Sioux vorgehen", verlangte General Sherman, "selbst wenn wir sie dabei auslöschen, gegen Männer, Frauen und Kinder."
Es war eine leere Drohung. Obwohl das kalte Wetter die Indianer zwang, ihre Belagerung zwischenzeitlich abzubrechen und geschützte Lager aufzusuchen, setzten sie ihre Angriffe im folgenden Jahr, 1867, fort. Auf Druck der Friedensbefürworter im Osten hin gelangte die Regierung schließlich zu der Ansicht, daß sich der finanzielle und militärische Aufwand für den Bozeman Trail nicht lohnte, und gab auf. Solange die Soldaten durch Red Clouds Angriffe damit beschäftigt waren, sich selbst zu verteidigen und zu versorgen, konnten sie niemanden schützen, und somit war die Route nach wie vor viel zu gefählich. Außerdem, so versuchte die Regierung sich selbst zu trösten, würde der Bozeman Trail bald nicht mehr benötigt, sobald die transkontinentale Eisenbahn fertig war und damit kürzere und sicherere Strecken in die Bergbauregionen Montanas zur Verfügung stehen würden.

1868 verkündete die Armee den Indianern, daß sie die Forts aufgeben würde. Gleichzeitig lud eine Kommission, zu der auch General Sherman gehörte, Red Cloud und die Häuptlinge der mit ihm verbündeten Gruppen zu einer Versammlung in Fort Laramie ein, um einen Friedensvertrag zu unterzeichnen. Red Cloud und viele der führenden Häuptlinge weigerten sich, dorthin zu kommen, bevor die Soldaten tatsächlich abgezogen waren, doch diejenigen, die der Aufforderung folgten - darunter Sinte Gleshka -, setzten ihr Zeichen unter die ihnen vorgelegten Verträge. Es schien ein vollkommender Sieg der Indianer zu sein, die um ihr Land gekämpft hatten. Im Juli und August verschwanden die Soldaten schließlich aus dem Land am Powder River und überließen die verhaßten Forts den Kriegern, die sie sofort in Brand steckten. Dann wurde Red Cloud von einem Rat der Oglala ermächtigt, mit der Autorität eines Friedenshäuptlings mit den Weißen zu sprechen. In Begleitung von hundertfünfundzwanzig Kriegshäuptlingen und Führern der Oglala, Hunkpapa, Sicangu, Sihasapa und Sans Arc ritt er nach Fort Laramie, um den Vertrag zu unterzeichnen.

Red Dog, Little Wound, J. Bridgeman (Dolmetscher), Red Cloud, American Horse und Red Shirt

Tage des Aufruhrs
Red Clouds Beziehungen zur amerikanischen Regierung blieben jedoch gespannt. Er und die anderen Häuptlinge, die den Vertrag unterzeichnet hatten, gingen davon aus, daß man ihnen damit versprochen hatte, die Indianer könnten in ihrem Land in Frieden leben, und Soldaten und andere Weiße würden ihren Jagdgebieten fernbleiben. Außerdem glaubten sie, sie könnten den Handel um Waffen, Schießpulver und Blei - Dinge, die sie für die Jagd benötigten - mit den Posten am Platte River wieder aufnehmen, der vor Chivingtons Massaker an den Cheyenne jahrelang friedlich verlaufen war.
Red Cloud und die anderen Häuptlinge mußten erkennen, daß die Regierung Pläne verfolgte, von denen sie den Indianern nichts gesagt hatte. Zum einen sollte das ganze Gebiet westlich des Missouri im heutigen South Dakota als Reservation eingerichtet werden, wo alle Westlichen Sioux leben mußten; ihre Agentur sollte Fort Randall am Missouri sein, ein Posten in der südöstlichen Ecke der Reservation, der weit entfernt von den Bisonrevieren lag. Zum zweiten gestattete der Vertrag den Indianern, weiterhin im Land am Powder River zu jagen, doch war diese Vereinbarung der Regierung aufgezwungen worden, und so betrachtete sie sie nur als vorübergehend gültig. Das Gebiet zwischen den Black Hills und den Bighorn Mountains, das Red Clouds Leute so heftig verteidigt hatten und das in der geplanten Reservation nicht enthalten war, sondern schwammig als "nicht abgetretenes Land" bezeichnet wurde, mußte möglicherweise an Weiße aus Montana, Wyoming und South Dakota abgetreten werden, die schon jetzt das Recht verlangten, in den Bighorn Mountains nach Gold zu suchen.
Zum dritten wollten die Eisenbahngesellschaften den Bau der Union Pacific Railroad entlang des Platte River rasch vorantreiben; zur Finanzierung ihres Vorhabens beabsichtigten sie, das ihnen zugesprochene Land im Tal des Platte River zu verkaufen. In Washington plante man, alle Sioux nach Norden in die neue Reservation in South Dakota umzusiedeln, wo sie den Bau der Eisenbahnlinie nicht behindern konnten. Der Handel mit den Posten am Platte River sollte ihnen verboten werden.

Als die Indianergruppen, die um das Land am Powder River gekämpft hatten, die Absicht der Regierung erkannten, wurden viele von ihnen, einschließlich den Anhängern des aufstrebenden jungen Kriegsführers Crazy Horse, mißtrauisch gegenüber Red Cloud, weil er offenbar einen Vertrag unterzeichnet hatte, in dem eine Reservation und eine entlegene Agentur vorgesehen waren. Doch Red Cloud betonte, daß der Friedensvertrag nichts dergleichen enthalten hatte, und verlangte, nach Washington gebracht zu werden, um die Angelegenheit zu klären. Aufgrund seines Widerstands gegen die Soldaten im Land am Powder River war er für die weißen Amerikaner zum berühmtesten Indianer geworden, der insbesondere bei Friedensbefürwortern, Menschenfreunden und Reformern im Osten großes Ansehen genoß. Mit ihrer Unterstützung bekam er die Erlaubnis Präsident Grants, in die Regierungshauptstadt nach Washington zu reisen.
1870 fuhren Red Cloud und eine Delegation von Indianern mit der Eisenbahn nach Washington. Doch der Plan der Politiker ging nicht auf. Red Cloud und die anderen Häuptlinge traten stolz und würdevoll auf und ließen sich von den Sehenswürdigkeiten und Unterhaltungsveranstaltungen nicht beeindrucken. Nach einer höflichen, aber unterkühlten Begegnung mit Grant setzten sie sich mit dem Innenminister an die Arbeit, der ihnen erklärte, sie müßten ihr Volk zu den Agenturen in der neuen Reservation führen. Als Red Cloud dieses Ansinnen zornig zurückwies, wurde den Häuptlingen der Text des Vertrags in ganzer Länge vorgelesen. Es war offenkundig, daß sie vieles davon noch nie gehört hatten. Red Cloud wurde wütend und sagte, das Papier enthalte zahllose Lügen. "Ich höre hier zum erstenmal von einem solchen Vertrag", sagte er. "Ich habe noch nie etwas davon gehört und beabsichtige nicht, ihn zu befolgen." Als man ihm eine Kopie des Vertrags überreichen wollte, wies er sie zurück und wiederholte: "Darin stehen lauter Lügen."
Zahlreiche Reporter waren Zeugen des Treffens. So schrieb The New York Times:

Wir würden in den Kongreßberichten im Globe von einem ganzen Monat umsonst nach einer Rede suchen,
die so interessant war wie diejenige, die Red Cloud gestern beim Indian Council vortug ...
Diese klare Vorstellung dieses leseunkundigen Wilden dessen, was er als seine Rechte darstellt, und dessen,
was er als Unrecht betrachtet, zeigt deutlich die Notwendigkeit, auf aufrichtige und verständliche Art mit
den Führern der eingeborenen "Nationen" zu verhandeln. Der Versuch, die Indianer zu beschwatzen und
zu betrügen, als hätten sie keinerlei Intelligenz, muß aufhören, ebenso wie die Politik, sie wie wilde Tiere
zu jagen.

1868 kamen Männer zu uns und brachten Papiere mit. Wir konnten sie nicht lesen,
und sie sagten uns nicht, was darin stand. Wir dachten, der Vertrag besagt, daß sie
die Forts räumen würden und wir zu kämpfen aufhören ...
Als ich nach Washington kam, erklärte mir der Große Vater, was wirklich in dem
Vertrag stand, und zeigte mir, daß die Dolmetscher mich hintergangen hatten. Alles,
was ich verlange, ist recht und billig.
Ich möchte wissen, warum Beauftragte zu uns geschickt werden, die nichts tun, als
uns zu bestehlen und uns die Reichtümer dieser Welt wegzunehmen.

In der Zwischenzeit wuchs das Mißtrauen der Sioux-Gruppen gegen Red Cloud; ihnen mißfielen sein Ehrgeiz und sein gebieterisches Auftreten, und sie warfen ihm vor, sich den Weißen für ihre Geschenke und ihre Gunst verkauft zu haben. Nur rund zwei Drittel der Oglala folgten ihm zu der neuen Agentur. Die anderen, die ihm die Verteidigung ihres Landes nicht mehr anvertrauen wollten, blieben am Powder River oder zogen nach Norden in die Büffelregionen von Montana, wo sie sich Sitting Bulls Hunkpapa-Sioux und anderen nördlichen Teton-Gruppen anschlossen. Sie bewunderten die mutige, kompromißlose Führerschaft des Oglala-Kriegers Crazy Horse, der sich gegen Red Cloud stellte. 1872 fühlten sich diejenigen, die das Vertrauen in Red Cloud verloren hatten, bestätigt, denn Red Cloud schickte im Namen der Regierung seine Kapitulation an Sitting Bull und die anderen Häuptlinge im Norden:

Freunde, ich führte mit euch den Krieg gegen die Weißen, bis ich vor zwei Jahren meinen Großen Vater
(den Präsidenten) besuchte. Mein Großer Vater sprach gut zu mir. Ich nahm seine Worte in mich auf
und kehrte heim. Ich bat um viele Dinge für mein Volk, und er gab mir diese Dinge. Ich werde nicht mehr
gegen die Weißen in den Krieg ziehen. Ich werde tun, wie mein Großer Vater mir sagt, und mein Volk
dazu bringen, daß es auf ihn hört. Ihr müßt den Krieg alleine weiterführen. Für mich ist er vorüber.