In 1857, Wells Fargo joined other express companies to form the Overland Mail Company, establishing regular twice-a-week mail service between St. Louis and San Francisco. Wells Fargo had the route surveyed and shared in the financing.

Nicknamed the “Butterfield Line” after its president, John Butterfield, it ran 2,757 miles through the Southwest via El Paso, Tucson and Los Angeles and then up through California’s Central Valley to San Francisco.

Night and day the stage rolled on at a pace from 5 to 12 miles an hour across vast, treeless plains, jagged mountain passes, scorching deserts and rivers cursed with quicksand. The coached stopped only to change horses or let passengers slug down a cup of coffee with their beef jerky and biscuits. About 25 days later, it clattered into San Francisco!

In 1861, the Civil War forced overland staging to a central route across the Great Plains, through the Rocky Mountains, into the Great Basin, and over the Sierra Mountains.
Along this mail route, passengers and Wells Fargo’s express rode the stages of the Pioneer Stage Line from California to Virginia City, Nevada. The Overland Mail Company, by now under Wells Fargo’s control, ran coaches from Virginia City to Salt Lake City, Utah. There mail and passengers connected with Ben Holladay’s Overland Express running through Denver, Colorado, and eastward to the Mississipi.

The Pony Express was established to prove that the nation’s mail could be carried across the West swiftly on the central route. From April 1860 to October 1861, young riders relayed mail across almost 2,000 miles from St. Joseph, Missouri to Sacramento, California in only 10 days. In its final months, the Pony Express became part of the stagelines’ U.S. Mail contracts. The Wells Fargo-run Overland Mail Company operated the Pony from California to Salt Lake City.

In 1866, Wells Fargo bought out Ben Holladay's expanding network and combined it with the Pioneer and the Overland Mail stagelines to create the largest stagecoach empire in the world. Stagecoaches carrying the Wells, Fargo & Co. name rolled from Nebraska to California via Denver and Salt Lake City. From Denver, coaches served the mining towns of the Rockies, and from Salt Lake City, they carried mail and passengers to Montana and Idaho.

Gold brought miners to the mountains of Montana and Idaho, and Wells Fargo's stagecoaches carried it out. W. H. "Shotgun" Taylor supervised the stage operations, and hired drivers who could handle a team of horses around mountain roads with calm grace.

In 1869 at Promontory, Utah, dignitaries hammered in a Golden Spike which joined the rails of the Transcontinental Railroad – and ended Wells Fargo’s overland stageline operations.

However, stagecoaches continued rolling wherever the railroads did not. Wells Fargo contracted with independent stageline operators to carry treasure boxes and express, even into the early 20th Century.