Challen unsuccessfully stood for parliament at the 1992 general election in the constituency of Beverley. He finished in third place and more than 22,000 votes behind the winner James Cran. He entered parliament at the 2001 general election for Morley and Rothwell following the retirement through ill health of Labour MP John Gunnell. Colin Challen was elected with a majority of 12,090 and made his maiden speech on 25 June 2001, in which he spoke of Herbert Henry Asquith who was born in Morley. He was re-elected at the 2005 general election, retaining his seat with a majority of 12,343.