The Robert E. Lee is among the best-known steamboats built in New Albany. Completed in 1866 for Captain John W. Cannon, the Robert E. Lee cost $230,000 and was designed to be the fastest and most luxurious steamboat on the western rivers. Its inaugural voyage took place in October 1866. Soon, the Robert E. Lee began setting speed records and winning over passengers. Ship captains competed to set fast times on common routes during the heyday of river transportation. Speed records became a source of pride and demonstrated technological progress. In an era of dramatic increases in travel speeds, having a fast boat attracted freight shipments and passengers.

The Robert E. Lee measured 285 feet long and 46 feet the beam. Its pilot house stood 30 ½ feet above the main deck and eight boilers supplied power to two paddle wheels, each 38 feet in diameter and 17 feet wide. As its reputation grew, Captain Thomas P. Leathers, a longstanding rival, commissioned construction of a steamboat called the Natchez. Designed to be faster than the Robert E. Lee, the Natchez was slightly larger but similarly outfitted.

For a time, Cannon resisted invitations to race the Natchez. During the summer of 1870 he relented by agreeing to race from New Orleans and St. Louis, a distance of 1,200 miles. The race began in New Orleans on June 30 at 5:00 p.m. The Robert E. Lee left its wharf as soon as the starting shot rang out. The Natchez departed five minutes later. The race remained close during the next several days but the Robert E. Lee eventually prevailed. It arrived in St. Louis at 11:20 a.m. on July 4 after three days, 18 hours, and 14 minutes. The Natchez followed six hours and 36 minutes later.

The race quickly became an international sensation, attracting attention across the United States and Great Britain.

Cannon continued to operate the Robert E. Lee on the Mississippi and other rivers in the years that followed. On September 30, 1882, the steamboat caught fire near Point Pleasant, Louisiana, thirty miles north of New Orleans. Twenty-one people died in the blaze and nearly all of the cargo perished. The Robert E. Lee lives on in lore and legend as one of the most celebrated paddle-wheel steamers in American history.