This became the primary motive power depot of the London Chatham & Dover Railway, providing all locomotives for the services out of the company's nearby terminus Victoria. It was opened in February 1862 as part of the company's endeavour to provide proper facilities - indeed, its trains were still terminating at temporary accommodation at Victoria until a new station on the West End site was opened to traffic in August of the same year. Longhedge Works and Goods Depot also opened in 1862, completing a large complex within a maze of lines created by the LC&DR and LB&SCR. The first shed arrangement at what was first known as ''Battersea'' was of the semi-roundhouse type, served by no less than twenty-two lines feeding off a turntable. By 1880 the LB&SCR also had impressive shed facilities, having constructed three roundhouses around the viaduct approach to Victoria, north west of the LC&DR's Battersea accommodation. 1881 saw the replacement of the semi-roundhouse at Battersea with a standard dead-end, sixteen parallel line arrangement, in conjunction with the enlargement of the locomotive works at the site.
Throughout SE&CR days this shed remained the principal motive power depot for the Kent lines, followed closely in second by the ex-SER establishment at Ashford. It was not until the Southern Railway rebuilding of the depot during 1933 and 1934 that it became known as ''Stewarts Lane'', after a nearby road (which is no longer in evidence today). SR modifications in this year were undertaken to accommodate those remaining locomotives transferring over from the nearby ex-LB&SCR roundhouses, whose predominantly suburban locomotive allocation had dwindled since electrification of such routes shortly after the Grouping. Unlike the LC&DR's main line, however, the ''Brighton'' line had never been served by a substantial London-based shed accommodating the major express locomotives; such engine supply was provided by the colossus at the namesake seaside resort. With the disbanding of the Battersea roundhouses, Stewarts Lane provided a number of locomotives for what became the Central Division, but Brighton always remained the ultimate supplier of traction. The ''new'' Stewarts Lane featured a standard dead-end carriage cleaning depot behind the engine shed (formerly it worked on a traverser), the turntable had shifted from a position adjacent to the locomotive shed to one several hundred foot westwards, but the buildings of Longhedge Works remained. In the meantime, the engine shed had received a new asbestos roof, new water facilities were provided and a tall coal plant built. As a consequence of the depot improvements, Stewarts Lane was capable of handling an allocation of up to 170 locomotives, the largest on the whole Southern Railway network.
Similar to many engine sheds and stations based in the capital, the depot suffered bomb damage during World War II, but this was subsequently ''patched up'' and the shed remained the prime locomotive supplier for the South Eastern Division after Nationalisation. It would be the Kent Coast Electrification Scheme which would result in the ultimate demise of the steam shed, modification work at the site beginning in 1957. That included the demolition of the old Longhedge Works buildings, the building of a new three-road electric depot alongside the carriage & wagon repair shed and the installation of third rail on all lines excepting those of the steam shed and carriage & wagon repair building. With the electrification of the ''Chatham'' line on 15th June 1959, steam locomotive numbers dwindled considerably, electric multiple units assuming main line services, with E5000 and E6000 series (Class 71 & 73) electric locomotives also appearing in that year. The steam shed remained operational for some years later, although was dealt yet another blow with the electrification of the Sevenoaks, Tonbridge and Ashford route in June 1962, but even by this time its regular steam workings were in single figures. Closure finally came in 1963, many of the locomotives transferring to the South Western Division, where steam traction was being phased out much less rapidly. The former steam shed remained largely complete until 1967, when a fire broke out and destroyed the roof. This was followed by partial demolition of the structure, but all shed lines were left in situ and the two most westward lines retained their roofs, these of which were renewed after the aforementioned fire. The covered shed lines were used for servicing diesel locomotives, incorporating a fuel tank and refuelling pumps. During the electrification of the lines the carriage cleaning shed was enlarged and modified for the maintenance of EMUs and remaining locomotive-hauled stock.
From 1982 there were three main users of the depot: London & SouthEast, Railfreight and the Venice Simplon Orient Express [British Pullman]. From May 1984 onwards the depot played host to the InterCity Business Sector when the re-branded ''Gatwick Express'' got underway - Class 73/2 Electro-Diesels, Class 489 GLV vehicles and former Midland Region BR Mk 2f stock was now based here. In June 1986, ''Network SouthEast'' replaced the ''London & SouthEast'' brand at the depot and from October 1987 onwards, ''TrainLoad Construction'' replaced plain old ''Railfreight'', as further divisions of the latter were made to re-brand individual commodity traffic. ''Railfreight Distribution'' also arrived at the same time. It was then on 10th April 1988 that Stewarts Lane officially became a depot of the InterCity Business Sector, by which time it was home to eighty-seven Mk 2f carriages and forty-seven Class 73s (not all of which were Gatwick Express-dedicated). The Civil Mechanical & Electrical Engineers department also appeared at the site with the disbanding of the Regions in April 1991. After privatisation, however, the depot had come full circle and again it began to decline, just like when steam was being phased out in the area during the late 'fifties. English, Welsh & Scottish Railway took over the functions of the TrainLoad sectors (which had since been formed into shadow franchises ''Mainline'', ''Transrail'' and ''Loadhaul'') on 24th February 1996, followed by ''Railfreight Distribution'' on 22nd November 1997. However, the then newly-privatised operator closed their only presence at the site, which was the fuel and maintenance depot, this officially being taken out of use at 16:30 on Saturday 28th September 1997. The Network SouthEast operation had been taken over by franchise holder ''Connex South Eastern'' and the Gatwick Express operation by ''National Express''. The EWS establishment, which was the former roads of the engine shed (including the covered portions) were torn up and replaced by a concrete terminal. However, two walls of the original engine shed still remain.
Meanwhile, at the end of September 1990, construction of a new viaduct had begun at Stewarts Lane. The viaduct was designed to allow the passage of Eurostar services from the South Western Division main line, onto the South Eastern Division. 410 yards east of Queens Road station, the double-track international line was to leave the course of the Waterloo approaches, and begin curving over the six domestic tracks in a southward direction. This called for a 361 foot long rectangular cover to be put over the domestic tracks at this point, this comprising some 1,500 square metres of brickwork, seventy steel beams (each 20 tons in weight), and 4000 cubic metres of reinforced concrete. The viaduct itself was able to assume a course which avoided the need to demolish existing buildings, and the structure was clad with dark green noise absorption panels to minimise residential disruption. The line joined the triple track from Victoria at what is now called ''Linford Street Junction'', some 1½ route miles out of Victoria. The then new viaduct was deemed officially complete on 24th March 1992, being opened by the Mayor of Wandsworth. The track and 7000 tons of ballast had yet to be laid.