On 13 June 2006, Peter Taylor left Hull to take up the job vacated by Dowie at Crystal Palace, a club at which he had enjoyed considerable success as a player. Phil Parkinson was confirmed as his replacement on 29 June 2006, with Hull paying Colchester (with whom Parkinson was still under contract) £400,000 compensation. Phil Brown, who had recently departed his job as manager of Derby County, joined the club as Parkinson's assistant.
Defender Leon Cort became Hull's first million-pound player when he followed Peter Taylor to Crystal Palace for a fee of £1,250,000. Parkinson wasted no time in spending the majority of this money on strengthening the City squad in readiness for the 2006–07 season.
Chairman Adam Pearson stated his ambition to take Hull into the top flight for the first time in their history – and he believed Phil Parkinson was the manager to do it. However, their dismal start to the 2006–07 season was hardly the form of a team attempting to gain promotion, and on 4 December 2006 Parkinson was sacked as manager with Hull in the relegation zone, despite having spent over £2 million on players.
Phil Brown was appointed as caretaker manager and by 4 January 2007, Hull had moved out of the relegation zone and Brown was rewarded with a contract as their new manager until at least the end of the season.
Hull City all but secured their place in the Championship next season with a 1–0 victory away at Cardiff City, on 28 April 2007. This left them 3 points clear of Leeds United, the only side with a chance of overtaking them, but with a vastly superior goal difference this was only a mathematical possibility. This crucial goal was scored by Dean Windass, who had rejoined his hometown club on loan from Bradford City. By 4 May, due to a lack of any realistic chance of them remaining in the Championship, Leeds went into administration and in doing so received the 10 point penalty such a move incurs. This deduction left Leeds at the bottom of the championship on 36 points, securing Hull's place in the Championship for the 2007–08 season.