He was signed by Start in 2001, and debuted in the Norwegian Premier League in 2002, when the youthful Start squad only made 11 points and were relegated.
After two seasons in the First Division, Start were once again promoted in 2004, with Hæstad as one of the team's central players. Hæstad has continued in great form after the promotion, and was named player of the month by NRK in April 2005.
On 29 December 2006 it was announced that Wigan Athletic had secured Hæstad on a 6 months loan contract. The Wigan boss, Paul Jewell expressed delight on signing the talented midfielder. The Norwegian newspaper VG would later reveal that it not was a standard loan contract, but an intricate deal that could see Hæstad stay at Wigan until July 2010, if they pick up an option to buy him at the end of the current season. Hæstad made his Premier League debut on 13 January 2007 against Chelsea, but was released from his loan contract at Wigan Athletic by mutual consent on 1 April 2007.
Hæstad made a scoring return for Start on his return to Norway after scoring the fourth goal in a 4–2 victory away to Aalesund
On 2 January 2008, Kristofer Hæstad signed a four-year contract with Vålerenga. On 29 March 2008, Hæstad made his competitive debut for Vålerenga in the season's first game against Aalesund. After a poor first season plagued by injuries, and failing to score a goal, rumors said that he was heading away from the club, most likely back to his former club Start. However, he stayed at Vålerenga and had a great second season.[according to whom?] He scored his first goal against Start in a 2–3 loss. He also scored two goals against Lyn which ended 4–4.