In 1846 the Grand Junction Railway Company obtained an Act of Parliament to build a bridge to cross Runcorn Gap. A time limit of 7 years was imposed. Shortly after obtaining the Act the Company amalgamated with others to form the London and North Western Railway. Other projects took precedence, the 7 years time limit passed, and so the powers to build the bridge lapsed.

In 1861 Parliamentary approval for a bridge was again obtained with the intention of reducing the distance from Crewe to Liverpool, as the GWR route to Birkenhead was shorter, though it did require a ferry across the Mersey. Work commenced in 1863 and the first stone was laid in 1864. The bridge was completed by 1868 and on May 21st there was an introductory opening when the contractor's locomotive drew 20 wagons over the bridge. It was formally opened for traffic on 10th October. The first goods traffic crossed it on February 1, 1869 and the first passenger train crossed on April 1st of that year.

The bridge consists of three wrought iron spans of 93 m. (305 ft.), each on two sandstone abutments with foundations at a depth of about 14 m.(45 ft,) below water level. It carries a double line of tracks, with a footpath for pedestrians on its eastern side. It has a clearance of 23 m.(75 ft.) above the high water mark to allow sailing ships to pass beneath it. There are 6 lattice girders, two to each span. Each girder contains 700 tons of iron and is fastened by 48,115 rivets. From the north side of the river the bridge is approached by a viaduct of 49 arches, then a short piece of embankment, followed by 16 more arches. From the south it is approached by a viaduct of 33 arches. At the time of construction, the bridge was the longest in the world.

It is named after Aethelfleda because the southern abutments and pier were built on the site of the Saxon castle erected by her in 915. Parts of the bridge are castellated to reflect this. There are three shields above the footway showing, from the southern end, the Coat of Arms of the City of London, Britannia (from the crest of the railway company) and the Liver Bird of Liverpool. Because of the crest the bridge is also known as the Britannia Railway Bridge.

In the 1890s the Manchester Ship Canal was built and ships were able to pass under the bridge. The footway was closed in 1965. It is a listed building Grade II*. (see also entry Silver Jubilee Bridge, Runcorn).