1865 campierte Generalmajor Grenville M. Dodge mit seinen Truppen an der Stelle des heutigen Cheyenne, als er damit beauftragt war, eine geeignete Route für eine Eisenbahnlinie über die Laramie Mountains zu finden, wobei die Lokalität als geeigneter Siedlungspunkt ausgemacht wurde.[3]
Als Dodge zwei Jahre später zum Chefingenieur der Union Pacific Railroad ernannt wurde, gründete er an der Stelle des heutigen Cheyenne eine zunächst als provisorisch betrachtete Ansiedlung. Im Juli 1867 ließen sich die ersten Siedler dort nieder, als die Union Pacific Railroad hier einen Bahnhof errichtete.[3] Benannt wurde die Stadt nach dem dort ansässigen Volk der Cheyenne (eigentlich Shey’ an’ nah), einer Gruppe der Algonkin.[3]
Mit der Eisenbahn kamen viele Siedler und bald besaß die Stadt rund 60 Bordelle und Saloons. Mit den Eisenbahnarbeitern kamen auch zahlreiche Händler und Spekulanten in die Region, welche hier auf gute Geschäfte hofften. Zum Jahreswechsel 1867/68 hatte Cheyenne bereits 4000 Einwohner. Bereits 1868 wurde Cheyenne zur Hauptstadt des Laramie-County ernannt und ein Jahr später wurde die Stadt zur Hauptstadt des neu gegründeten Wyoming-Territoriums.[4]
Ab etwa 1870 stieg Cheyenne zu einem Zentrum der Rinderzucht auf, welches besonders für den europäischen Markt produzierte, wobei ab ca. 1880 zahlreiche „Viehbarone“ in die Gegend um Cheyenne kamen. Ab 1875 wurde in der Umgebung von Cheyenne außerdem Gold abgebaut, was erneut viele Siedler in die Region trieb.[4]
1890 wurde Cheyenne, welches mittlerweile rund 10.000 Einwohner hatte, zur Hauptstadt des dann zum Staat erhobenen Territoriums Wyoming ernannt. Im selben Jahr wurde mit dem Bau des Wyoming State Capitols begonnen.[4][5] Noch vor der Jahrhundertwende stellten sich viele Rinderzüchter der Region auf die Haltung von Schafen um, welche sich deutlich besser an die gegebenen klimatischen Verhältnisse von Cheyenne anpassen konnten als Rinder. Bis heute spielt die Schafhaltung in der Gegend von Cheyenne eine wichtige Rolle. Während des 20. Jahrhunderts entwickelte sich Cheyenne zunehmend zu einem Industriestandort.[3]
Cheyenne ist auch heute noch ein Zentrum der Viehzucht(Cowboy Capital). Seit 1897 finden jedes Jahr die Frontier Days statt, ein Festival mit über 300.000 Besuchern.