The introduction of the Crossrail Bill "at the earliest opportunity" was announced in Parliament by the then Secretary of State for Transport, Alisdair Darling, on 20th July 2004. The Crossrail Bill was subsequently brought to Parliament on 22nd February 2005 and the Crossrail Act was passed on 22nd July 2008. The scheme was estimated to cost £10,000,000,000 at 2004 prices and involved constructing a cross-London route linking Maidenhead in the west to Shenfield (Essex) and Ebbsfleet International (Kent) in the east. In November 2004, it was decided to cut the Ebbsfleet section of the line back to Abbey Wood. Reliability of Crossrail services could not be guaranteed on an already busy North Kent Line, which would require large investment to increase capacity.
1⅓-miles west of a rebuilt station at Abbey Wood, the Crossrail line was to plunge into a tunnel at Plumstead. This was going to be twin-bore, 1.64-miles in length, and be one of five tunnels along the new line. It was to reside 50-feet below the Thames, be the only place where the line crossed the river, and join twenty-three existing tunnels under the riverbed. The contract for these works was worth £200 million and this was awarded to joint venture partners HOCHTIEF Solutions AG and J. Murphy & Sons. This was the same partnership which built the 1.86-mile-long twin bore Thames Tunnel between Thurrock and Swanscombe on the CTRL.
Construction work began at the former Plumstead station goods yard site in March 2012, starting with piling for the tunnel portal. In the following July, building of a treatment plant started, this of which would be used to process the slurry excavated from tunnel boring. The terrain to be bored comprised a mixture of chalk and flint, which the tunnelling machines destined for this area were designed specifically to deal with. The ground works at Plumstead were completed on 24th August 2012 and the two tunnel boring machines, named ''Mary'' and ''Sophia'', were due to arrive later that year.
On Wednesday 9th January 2013, boring of the first tunnel between Plumstead and North Woolwich commenced on the south side of the Thames. This used the 110-metre-long "Sophia" boring machine, which aimed to progress under the river at an average rate of approximately 100-metres a week. During the tunnelling process, the boring machine was able to convert waste soil into a slurry liquid for extraction. "Sophia" was equipped with a pressurised chamber, which mixed the soil with a combination of clay and water to allow it to be pumped out through a series of tubes as slurry. It eventually ended up at the aforementioned treatment plant located on the former Plumstead goods yard site. Here it was processed, the water being removed and the slurry turned into chalk cakes, these of which were then transported off site by road. As the tunnelling machine moved forward, precast segments were installed to provide a robust concrete lining within the bore.
On 19th May 2013, boring of the second tunnel began at Plumstead, this time using TBM "Mary". On 11th September of the same year, Crossrail Ltd received approval from Greenwich Council to construct a series of sidings on the "Whitehead Triangle" at Plumstead. The triangle was a mostly undeveloped site roughly bordered to its south by the proposed tunnel approaches and North Kent Line, to its north by Whitehall Avenue and the Southern Outfall Sewer, and to the east by residential property. It was proposed that the sidings would become a temporary facility to stable wagons used in connection with Crossrail construction, and would cease operation on completion of these works. However, it later became apparent that the site at Old Oak Common, which had been earmarked to stable and maintain Crossrail stock, did not have the capacity to accommodate the required number of units. Whilst a maintenance depot for Crossrail stock was still to be built there nevertheless, construction of the £142,000,000 complex having begun in January 2015, a planning appliction was submitted to lay permanent sidings at Plumstead, on the Whitehead Triangle. This morphed into "The Crossrail (Plumstead Sidings) Order 2015", which came into force on 21st April 2015. The advantage of this arrangement was that it allowed rolling stock to be stabled at the extremities of the operation, rolling stock sidings also being laid at Maidenhead and Shenfield.
The first TBM, "Sophia", reached North Woolwich on 29th January 2014; completion of the second tunnel, using TBM "Mary", came on 13th May of the same year. Crossrail tracks at the Plumstead site started to be laid in December 2014 and in the following May, a mile of double-track had been completed in the Abbey Wood direction. The yard on Whitehead Triangle, initially to be used by infrastructure trains and still under construction, saw the arrival of the first wagons of a colossal train in June 2015. Of the latter, this was a 465-metre-long (508.5-yards) formation of wagons, specifically designed to lay a concrete track bed within the tunnel bores. It travelled from France through the Channel Tunnel and at the terminal at Cheriton (Folkestone), each wagon was transported by road on low-loader, one-by-one, to Plumstead. Onward travel by rail was prevented by the fact that the Crossrail yard at Plumstead lacked a connection with the North Kent Line. Simialrly, GBRf Class 66 No. 66767 was brought by road to the site from Hoo Junction in the August to haul track-laying trains.
The amount of concrete to be laid for the track bed through all Crossrail bores amounted to over 50,000 cubic metres (65,398 cubic yards), forming part of a £250,000,000 contract awarded to a joint venture between Alstom, Travaux du Sud-Ouest (TSO), and Costain, to fit out the tunnels. The concrete train was scheduled to be deployed into service in September 2015.