The Great Western Railway considered a number of options for its London terminus, including sharing the London & Birmingham Railway's terminus at Euston. The London & Birmingham Railway had already been under construction for 2 years by the time the Great Western Railway obtained its Act of Parliament in 1835. Difficulties in agreeing space for depots and station facilities meant the sharing proposal was soon abandoned. Other proposals considered included terminating the line at Brentford, Edgware Road or Vauxhall Bridge, before the final choice of Paddington was made. In 1837 the GWR obtained an amendment to its Act of Parliament to enable a 4½ mile diversion of the proposed route from Acton to the new terminus at Paddington.
In the late 1830s, the Paddington area of London was a semi-rural residential district. The original station was a wooden structure built immediately to the west of Bishop's Walk (which was replaced by a new road (Bishop's Road) and bridge). The station consisted of two arrival platforms, one 255ft (78 metres) and one 340 ft (105 metres) long, and two departure platforms, both 235 ft (72 metres) long. To save space, hand operated traversers were used instead of points [switches] to add or remove carriages from trains. Most of the station offices were built into the arches of Bishop's Bridge. Access to the station was by an inclined roadway from Praed Street.
When the line opened through to Bristol in 1841, Paddington station handled 14 passenger and 2 goods trains each way on weekdays and 8 on Sundays. As the broad gauge network expanded to Exeter, Birmingham and South Wales, the station became overcrowded and in 1851 the directors decided to build a new station just over half a mile to the east of the first station at a cost of £50,000.
The original proposal was to retain the four platforms of the first station for arriving trains and use the new station for departures. In February 1853 this plan was amended to handle all traffic from the new station. The train shed at the new station was 700ft (215 metres) long and 238 ft (73 metres) wide in three spans, and did not require any extension until well after the demise of the broad gauge. Work also commenced on the hotel outside the station at the same time.
The train shed initially had ten lines - 5 facing platforms (although only three seem to have been used for normal traffic) and 5 sidings for coaches. The station opened for departures on 16 January 1854 and for arrivals on 29 May 1854, at which time the original station was demolished.
With the acquisition of the standard gauge Shrewsbury & Birmingham Railway (1854), Shrewsbury & Chester Railway (1854) and West Midland Railway (1863), the Great Western Railway needed to provide through standard gauge train services from London to the Midlands and north-west England. Despite the financial difficulties of the period, the line between Paddington and Reading was converted to mixed gauge to join the mixed gauge line between Reading and Wolverhampton. On 14 August 1861 the first standard gauge train entered Paddington and regular services between London and Birkenhead began in October 1861. Thereafter there was a steady increase in standard gauge services as broad gauge lines were converted to standard gauge, the majority in the early 1870s. Broad gauge trains continued to run from Paddington to Devon and Cornwall until the lines in those counties were converted to standard gauge in May 1892.