The bridge is named after former Florida governor Fuller Warren, former member and eventual denouncer of the KKK, who held the office from 1949 to 1953. He had previously served as a member of the Jacksonville City Council from 1931 to 1937.
The original bascule bridge was tolled until 1988, when the city of Jacksonville abolished toll collections. Increasing wear from heavy traffic, including a 1993 incident in which a 3-square-foot fragment of concrete broke loose, forced officials to ban large trucks from the bridge in 1998. It was permanently closed June 13, 2001, when all traffic was moved to the new Fuller Warren Bridge. After delays in removal because of legal and environmental concerns, the Florida Department of Transportation used explosives to complete demolition of the old bridge on February 17, 2007.
Conversion from the old Fuller Warren Bridge to the new one began with one lane of southbound I-95 traffic on April 16, 2000. The new bridge, built at a cost of approximately $100 million, was opened to all eight lanes in late 2002 and formally dedicated on January 13, 2003.