Millen was appointed as Steve Coppell's successor, after Steve chose to resign from Bristol City and retire from football. Millen spent most of his professional career at Brentford, where he reached the Associate Members' Cup final in 1985, and won the Football League Third Division in 1992. After leaving Brentford in 1994, he finished his playing career with Watford and Bristol City. Following retirement, Millen remained at City as a member of the coaching staff. He was caretaker manager at Ashton Gate following Gary Johnson's departure towards the end of the 2009–10 season. He took charge of nine competitive matches, winning five, drawing three and losing once. He was caretaker manager at Crystal Palace for 4 matches in the 2013-14 season winning one drawing one and losing 2. He was again appointed caretaker manager at Crystal Palace on 14 August 2014. However on 27 August 2014 Neil Warnock was appointed full time manager & at that time Millen's role at the club was not certain.
Following his retirement from football, Millen became under-17 manager at Bristol City. When Brian Tinnion was promoted to player-manager in 2004, he appointed Millen as his assistant. Under Tinnion's management City won 22 of 61 matches, and Millen was appointed as caretaker when Tinnion left the club. However, he publicly ruled himself out of the running to become the permanent manager. He was made caretaker manager of City when Gary Johnson left the club in March 2010, and became manager on a full-time basis on a three-year contract when Johnson's replacement, Steve Coppell, departed on 12 August 2010. Millen left the manager's position on 3 October 2011.
Millen was appointed the Head of Coaching and Development at Blackpool in July 2012.
Millen was appointed Assistant Manager at Crystal Palace in November 2012, following former Blackpool manager Ian Holloway. On 23 October 2013, Millen was appointed as caretaker manager after Holloway left by mutual consent.
On 26 November 2013, newly appointed Crystal Palace manager Tony Pulis announced that Millen will be kept as backroom staff. This is likely because Millen had successfully restored team spirit back into the Crystal Palace squad and inspired Palace to 3 points closer to safety of relegation with 0-0 home draw to Everton, followed by a 0-1 win over Hull City away. 
After Tony Pulis' surprise departure from Crystal Palace on 14 August 2014 (only 2 days before the start of the new Premier League season) Millen was again appointed caretaker manager. However, when Neil Warnock was appointed permanent Manager on 27 August 2014, Millen's future was not made clear.