On 14 October 2001 the former Wales and West company of National Express Group, was divided into two, and the former Cardiff Railway Company (Valley Lines) was added to the new Wales and Borders company, based in Cardiff, together with the lines from Shrewsbury to Pwllheli and Aberystwyth formerly operated by Central Trains.

In September 2003 the lines west of Crewe, through Chester to Holyhead, Llandudno and Blaenau Ffestiniog previously operated by First North Western trains were transferred to Wales and Borders. The company only ran the majority of trains in Wales and the Borders for about three months before the franchise ended.

In July 2003 the Strategic Rail Authority announced that from 7 December 2003 the franchise would be awarded for a 15 year period (subject to satisfactory reviews after 5 and 10 years) to Arriva.