In the mid-19th century, mail traffic between the eastern United States and the western states and territories was accomplished via Panama and Cape Horn. In 1857, Congress authorized the postmaster to contract a new overland mail service. The successful bidder for the southern route was John Butterfield, who agreed to convey mail twice weekly in 25 days per run. The "Oxbow Trail" originated at St. Louis, Missouri, and Memphis, Tennessee, then merged at Fort Smith, Arkansas. The stagecoaches traveled through Indian territory (later Oklahoma) and across northern Texas to Tucson, Arizona, and on to Los Angeles and San Francisco, California, traveling 2,795 miles from St. Louis.

The trail entered Grayson County by crossing the Red River at Colbert's ferry and proceeding into Sherman. It crossed the county toward Gainesville in Cooke County en route to Franklin (later El Paso). The citizens of Sherman are credited with especially courting the mail route to use Colbert's Ferry instead of entering Texas near Preston (8 mi. upriver). Sherman became a distribution point in 1858, bringing mail service to Texas settlements.

Waterman L. Ormsby of the New York Herald was the first through passenger on the Butterfield Trail in September 1858. He described Sherman as "a pleasant little village of about six hundred inhabitants," and chronicled the remainder of his trip across Grayson County, writing "our course lay across a fine rolling prairie, covered with fine grass, ...the beautiful moonlight lit up the vast prairies making its sameness appear like the boundless sea and its hills like the rolling waves." the southern route was terminated in March 1861. the course of the trail is still visible in a number of locations in Grayson County.