The Allegheny was first crossed at this point by a wooden bridge, built in 1856. This was replaced by the Sharpsburg Bridge in 1901, which was itself replaced in 1962, as it was deemed too narrow for the traffic volume that it carried.
The current bridge was completed on July 1, 1962 and is named for Robert D. Fleming, a former Republican Pennsylvania State Senator whose district featured portions of Pittsburgh's northeastern suburbs. It was built alongside and just upstream from the old bridge and consists of sixteen individual spans, including a 1,054 feet (321 m) long four span truss channel unit, with a 400 feet (120 m) span over the river and a 494 feet (151 m) three span girder section with a 227 feet (69 m) central span over the railroad.
A 200 feet (61 m) section of the bridge buckled when the Crescent Supply Co. warehouse beneath it was destroyed by fire on May 28, 1981. The bridge was finally reopened in January 1983.