Lexington began as a railroad siding on the Union Pacific when the tracks were laid through the area in 1866, but is was first called Plum Creek. The name came from a creek that flowed into the south side of the Platte River 17 miles southeast of the present-day site. The name was brought across the river in 1867 by Daniel Freeman, who ran a trading post on the Oregon Trail near the creek's mouth. Freeman moved north of the river as the railroad became the preferred way of travel for people heading west.

     Two years before the railroad arrived at Plum Creek, a tragic event occurred on the Oregon Trail south of the Platte River, near Plum Creek. A party of freighting wagons led by Thomas Morton was attacked in the early morning hours of August 8, 1864, by a renegade band of Cheyenne Indians. All 11 men in the party were killed and Morton's wife, Nancy Jane, and a young boy named Danny Marble, were taken captive. Mrs. Morton was held captive for six months before being ransomed and returned to her home in Iowa. The boy was released shortly after his capture, but died soon after. This attack led to the construction of Post Plum Creek, a military installation that protected travelers in the area between Fort Kearney and Fort McPherson.

     Plum Creek was designated as a post office in 1872, and two years later was incorporated as a town. The arrival of the first Philadelphia Colony that same year, along with those already here working on the railroad, farming, hunting or otherwise employed, made the first sizable community in the area.

     In 1873, the industrious new community built a bridge across the Platte, the first one west of Columbus, Nebraska, at a cost of $50,000. They funded the bridge through a property tax, nearly all of which was paid by the Union Pacific Railroad, the county's largest property owner!

     As Plum Creek grew and prospered, a growing number of its residents thought the name should be changed for several reasons. There was confusion with Elm Creek, just 18 miles away, and many thought the name wasn't representative of a progressive community. There were also some image problems due to some events such as the hanging of Mitchell and Ketchum by the Olive Cattlemen and the hanging of another unfortunate man by an angry mob in the county courthouse. In February of 1889, after several failed attempts with a variety of suggestions, the name of Lexington was chosen and agreed upon by the city officials. It appears the Olive family, who moved here from Texas, near the town of Lexington, may have had the last laugh.