Born in 1953 in Nottingham, he was educated at the local Robert Shaw Primary School in Aspley, Nottingham and Forest Fields Grammar School in Forest Fields. He graduated from City of London Polytechnic, and received an MA from the University of Leeds.
He joined the Labour Party in 1971 whilst working as a warehouse worker. He worked from 1978 to 1983 as a Research Officer with the Labour Party. In 1982 he was elected as a councillor to the London Borough of Tower Hamlets, which he served until 1986. He was a local government officer at the Greater London Council between 1983 and 1984, before working for the trade union movement, running the first political fund ballots, and then with the GMB until his election in 1987.
Allen was elected as the Labour MP for the Nottingham North constituency at the 1987 general election, gaining the seat from the Conservative's Richard Ottaway with a majority of 1,665 votes. His majority at the 2010 general election was 8,138.
After helping to organise Tony Blair's leadership campaign, Allen was given a series of shadow portfolios, including social security, transport and the environment. After the Labour Party came to power at the 1997 general election Allen became a government whip until after the 2001 general election when he returned to the backbenches.
He opposed the Iraq War, and was at the forefront of a successful campaign to recall Parliament in September 2002, attempting to organise an unofficial recall if the House would not formally sit.
Allen sat on a number of parliamentary select committees and was the Chair of the Political and Constitutional Reform Select Committee in the House of Commons from 2010 to 2015 He is also a member of the Speaker's Committee on the Electoral Commission.
Allen announced he would stand down at the 2017 general election due to ill health.
Allen is a proponent of democratic reform and supports independent local government, some proportional representation and a fully elected House of Lords. He introduced a bill calling for a written constitution in the UK.
In 1995, he wrote "Reinventing Democracy" and in November 2002 he published The Last Prime Minister: Being Honest About the UK Presidency, claiming that the UK effectively had a presidency. He argued that the Prime Minister (or 'President', as he referred to the office throughout the book) should be directly and separately elected in order for a better separation of powers. This new arrangement, he argued, would be best spelled out "in plain English" in a written constitution.
Allen is a strong advocate of early intervention in social issues. He wrote "Early Intervention, good parents, great kids, better citizens" with Iain Duncan-Smith in 2009. He wrote two reports for the government on the topic in 2011.
In October 2005, Allen became the first MP to Chair a Local Strategic Partnership, which was subsequently renamed One Nottingham. Allen set it the mission of making Nottingham an "Early Intervention City".