The bridge was built in 1951 as the Veterans' Memorial Bridge to relieve congestion on the MacArthur Bridge to the south and was built as a toll bridge and 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 when the (free) Poplar Street Bridge was constructed, and traffic began to use that route, leading to declining toll revenues.
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. In 1987, the toll was removed. 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. It is now an important contributor to the transportation needs of the region and 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.