When the Great Exhibition of 1851 was transferred to Sydenham from Hyde Park, the West End of London and Crystal Palace Railway was formed to serve the new site of the exhibition. The terminus of the railway was at Stewarts Lane in Battersea on the south side of the river. In 1858, a joint enterprise, the Victoria Station and Pimlico Railway, was set up to take trains over the river. The railway was owned by four railway companies: the Great Western (GWR); London & North Western (LNWR); the London, Brighton and South Coast (LBSCR); and the London, Chatham and Dover Railway (LCDR).

The station opened in 1862 and was in two parts: the western side, occupied by the Brighton company, with six platforms and ten tracks, was fronted by a wooden building, and a hotel (the 300-bedroom Grosvenor).  The Chatham company occupied another rather shabby wooden-fronted building on the east side. This station had nine tracks and was shared by broad-gauge trains of the GWR. These arrived from Southall via the West London Extension Joint Railway through Chelsea. The approach tracks and station were built on the route and basin of the Grosvenor Canal.

The GWR remained part owner of the station until 1932, although its trains had long since ceased to use it. Each side of the station had its own entrance and a separate station master. Oscar Wilde inferred in 'The Importance of Being Ernest' that the Brighton side was socially superior.

At the start of the 20th century both parts of the station were rebuilt. Work on the Brighton side was completed in 1908 and was carried out in red brick and stone as an extension of the Grosvenor Hotel, which was rebuilt at the same time. The Chatham side, in an Edwardian style with baroque elements in white stone and designed by Alfred Bloomfield, was completed a year later. The two sections, sharply contrasting in appearance, were connected in 1924 when the Southern Railway removed part of a screen wall. At this time the platforms were renumbered as an entity.

An interesting solution to the problem of accommodating increasing traffic was found by the Brighton company. Unable to expand laterally due to the presence of Buckingham Palace Road, the platforms were extended lengthwise so that each could accommodate two trains, the inner one gaining access along a third middle track.

The eastern side of the station became an important terminal for boat trains serving the continent. During World War I it had became a terminus for trains carrying soldiers to and from France, many of them wounded. It became associated with luxury trains including the most famous, the Golden Arrow. The Night Ferry also operated to/from Victoria station. The western side became the terminus of the Brighton Belle in 1933, the world's only all Pullman electric train.

The area around the station became a site for other forms of transport: a bus station in the forecourt acquired from the railway by London Transport in exchange for the Transport Museum site in Clapham; a coach terminal to the south; for a time an international airline coach terminal, and more recently a terminal for trains serving Gatwick Airport.