The original terminal station was built in 1839-41 for the Great Western Railway (GWR). It was the first passenger railway in Bristol, and was designed by Isambard Kingdom Brunel, the railway's engineer. The station was on a viaduct to raise it above the level of the Floating Harbour and River Avon; the latter being crossed via the Grade I listed Avon Bridge. The station was covered by a 200 feet (61 m) train shed which was extended beyond the platforms by 155 feet (47 m) into a storage area and engine shed, which in turn was fronted by an office building in the Tudor style.

A few weeks before the start of the services to Paddington, the Bristol and Exeter Railway (B&ER) opened on 14 June 1841. Its trains had to reverse in and out of the GWR station. In 1845 the B&ER built its own station at right angles to the GWR station and an "express platform" on the curve linking the two lines, so that through trains to and from the London direction no longer had to reverse. The wooden B&ER station was known locally as "The Cowshed", but a grand headquarters was built at street level on the west side of its station in 1852-54 to the Jacobean designs of Samuel Fripp.

Additional railway routes put the two short - 140 yards (130 m) - platforms of Brunel's terminus under pressure and so a scheme was developed to extend the station. An enabling Act of Parliament was passed in 1865 and between 1871 and 1878 the station was extensively rebuilt. Brunel's platforms were extended by 212 yards (194 m) towards London, and a new three-platform through station was built on the site of the through platform, while the B&ER station was closed and the site used for a new carriage shed. It was at this time that the now familiar entrance building was constructed in French gothic style by Sir Matthew Digby Wyatt. It stands at the head of a wide approach road created between the two original station buildings.