The first, the London and Croydon Railway (L&CR), established a station on New Cross Road close to Hatcham in 1839. The second, the South Eastern Railway (SER), established a station near Amersham Way in the heart of New Cross in 1849. Both companies called their stations New Cross, and the earlier station became New Cross Gate when they came under the common ownership of the Southern Railway on 1 January 1923.

The original station was officially opened on 1 June 1839 by the London and Croydon Railway. Between February and May 1847 the station at New Cross was the northern terminus of the atmospheric propulsion system introduced by the L&CR, but in the latter month the system was abandoned by the new company.

During the 19th century, New Cross (Gate) became an important junction where the South London Line, the East London Line, and the Bricklayers Arms Line diverged from the Brighton Main Line to London Bridge.

The East London Railway was owned by a consortium of railway companies. Passenger services were operated by the London, Brighton and South Coast Railway (LB&SCR) between Croydon and Liverpool Street, and from 1884 by the Metropolitan District Railway between New Cross (Gate) and Shoreditch. LB&SCR services ceased on 31 March 1913, when the line was electrified using the fourth rail system and thereafter all passenger services were operated by the Metropolitan Railway. A separate ELR station was built but this was closed in 1886 and the trains were diverted to the adjacent LB&SCR station. The ELR station was then demolished and the site used for sidings.

In 1933 the Metropolitan railway was taken over by the London Passenger Transport Board, which operated services as part of the London Transport Metropolitan Line. London Transport was superseded by Transport for London, whose London Underground services temporarily stopped serving the station on 22 December 2007 for the East London Line to be converted into a National Rail line, reopening as part of the London Overground network on 27 April 2010.