Interest in a landmark bridge across the Missouri River arose after Omaha and Council Bluffs began replacing their older crossings with girder bridges which do not have towers (most notably the Ak-Sar-Ben Bridge). The bridge is named after former Nebraska Senator Bob Kerrey, who secured $18 million of federal funding for the bridge in 2000.
The bridge was redesigned in 2004 after the lowest bid for the project was $44 million. In May 2006, a final cable-stayed bridge design by Kansas City engineering and architectural firm HNTB was selected for the bridge. The $22 million bid included two 200-foot (61 m) towers and a clearance of 52 feet (16 m) above the river. Groundbreaking for construction of the bridge occurred on October 26, 2006.
The lights on the bridge were donated by Gallup, which has their corporate headquarters and Gallup University located on the Missouri River adjacent the Omaha landing of the bridge. The bridge lights include programmable controls that can display multiple colors in the large lights at the top of the towers and alter brightness and timing of the lights that run the entire length of the bridge. The lights were officially unveiled in a ceremony on September 13, 2008. The bridge lights were turned on while the Phil Collins song "In The Air Tonight" was played over a PA system. The event was accompanied by fireworks.
Due to safety concerns prompted by the 2011 Missouri River floods, the entrance on the Iowa side was closed on July 2 of that year. It reopened September 3, 2011.