club Sunderland on a free transfer. Upon signing a three–year contract with the club, he revealed that his ambition and desire to play at a higher level was the reason for him joining Sunderland. Sunderland were ordered to pay £150,000 to Oxford at an FA tribunal, to compensate for the time and money put into his development. Oxford would also receive 25% of any fee should Sunderland sell Whitehead. Whitehead made his Sunderland debut, coming on as a late substitute for Ben Clark, in a 2–0 loss against Coventry City in the opening game of the season. He quickly became a key member of the team, playing regularly despite facing competition from other midfielders. His run in the first-team saw him praised by manager Mick McCarthy. It wasn't until 25 October when he scored his first goal for the club, in a 1–0 win over Rotherham United. He then scored his second goal of the season on 11 December, in a 2–0 win over Cardiff City. Whitehead scored three more goals later in the season in games that ended up as Sunderland victories. Following his good performance at Sunderland halfway through the season, he was given a new three-year contract during 2004–05. Despite missing out three matches during the season, as he went on to make forty–three appearances and scoring five times in all competitions. He helped Sunderland to win the Championship in 2004–05, and was chosen as Players' Player of the Year by his teammates at the end of the season. In the 2005–06, Whitehead continued to establish himself in the starting eleven, with the club playing in the Premier League. Despite the club's struggles in the Premier League at the start of the season, he made a positive impact for the side. His performances earned him comparison to Manchester United's Roy Keane. It wasn't until 29 October when he scored his first Premier League goal, in a 4–1 loss against Portsmouth. Three weeks later, on 19 November, Whitehead scored his second goal of the season, in a 3–1 loss against Aston Villa. By November, he began playing in the right-wing position, a more unfamiliar role. On 26 November, Whitehead signed a contract extension with the club, keeping him at the Stadium of Light until 2010. He scored a swerving 30-yard free kick past then-England goalkeeper Paul Robinson in a 3–2 defeat against Tottenham Hotspur at White Hart Lane