The bridge replaced the Baytown Tunnel (of depth clearance 40 feet or 12.2 m). The tunnel had to be removed when the Houston Ship Channel was deepened to 45 feet (13.7 m), with a minimum 530 feet (161.5 m) bottom width, to accommodate larger ships. The last section of the Baytown Tunnel was removed from the Houston Ship Channel on September 14, 1999, with removal of the tunnel being the responsibility of the Texas Department of Transportation.
In October 1985 the Texas Highway department announced the project and estimated it would take two years to complete. Construction began in 1987 and was contracted by Williams Brothers and Traylor Brothers construction companies. In 1993, The firm selected to produce the steel, a Mexican company, went bankrupt. The contract was then awarded to a South African company which caused complaints because of the country's apartheid policies. After the completion date was pushed back several times, a letter was sent to the Texas Department of Transportation's executive director, William Burnett from the city of Baytown via the Baytown Sun in early 1995 which helped spur interest in finishing the project. Finally, on September 27th, 1995 the Fred Hartman Bridge has its grand opening ceremony hosted by Baytown Chamber of Commerce and La Porte Chamber of Commerce. Notable guests include George W. Bush, Miss Texas 1995, William Burnett and the Hartman family. Fred Hartman died in 1991 and did not live to see his dream come to fruition.