The bridge was built across the Mississippi River in 1951 as the Veterans' Memorial Bridge to relieve congestion on the MacArthur Bridge to the south. Built as a toll bridge, it was owned by the City of East St. Louis. At one time, it carried U.S. Route 40 and U.S. Route 66 across the river. In 1967, the bridge fell into disrepair after the (free) Poplar Street Bridge was completed; traffic moved to the new bridge, resulting in declining toll revenues needed for maintenance.
Eventually, ownership was transferred dually to the Missouri and Illinois departments of Transportation and the bridge was renamed after Martin Luther King, Jr. in 1968, after the national civil rights leader was assassinated in Memphis, Tennessee. In 1987, the states removed the toll for travel across the bridge. A bi-state project for about $24,000,000 to renovate the bridge, at the behest of local civic and government leaders, was carried out in the late 1980s. In the spring of 1989, the rebuilt bridge was reopened. In June 1990, the lighting of the bridge was completed by the St. Louis Port Authority. In the 21st century it is considered an important contributor to satisfying the transportation needs of the region and enhancing the ambiance of the historic St. Louis riverfront.
On October 12, 2009, the bridge was closed in order to reduce the old four-lane configuration down to three wider lanes, install a waterproofing membrane over the bridge surface , and to install a concrete barrier to separate eastbound traffic from westbound. Over the previous six years there had been 38 serious accidents, including several involving multiple fatalities. The $1.4 million project was aimed at eliminating these head-on collisions in the future. The bridge re-opened on October 21, 2009.
After the new Stan Musial Veterans Memorial Bridge opened in February 2014 across the river, daily traffic volume on the King bridge had decreased by 40% by April 2014 to 12,700 daily. This was one of the goals of construction of the new bridge: to distribute traffic more widely among the bridges and associated roadways, improving traffic patterns.