Kilgallon played in York City's youth system before signing for Leeds United at the age of 12. He signed schoolboy forms with the club in 1998, before being offered a three-year scholarship the following year. He signed a one-year professional contract with Leeds at the end of his scholarship. Kilgallon was first called up to the first team for a UEFA Cup match away to Metalurh Zaporizhya on 3 October 2002, although he did not make the matchday squad. In his first season in the Championship with Leeds, he was mainly playing left back with Paul Butler and Sean Gregan the main centre-back partnership. Kilgallon also displaced Clarke Carlisle and Michael Duberry in the pecking order. He played in their run to the 2006 Championship play-offs, helping them make the final, which Leeds lost 3–0 against Watford at the Millennium Stadium. Kilgallon was the subject of a failed bid of over £1 million from newly promoted Premier League club Reading in August 2006. He played in most of Leeds's matches of the first half of the 2006–07 season, keeping experienced centre-backs Paul Butler, Sean Gregan and Hayden Foxe out of the team.
Sheffield United
Kilgallon signed for Premier League Sheffield United on 8 January 2007 for a £1.75 million fee, rising to £2 million with add-ons. Despite recovering from an early injury, he did not make his debut until starting in a 1–0 loss away to Bolton Wanderers on 31 March 2007. Having been used sparingly in the Premier League, Kilgallon established himself in the team in the Championship. He scored his first goal for Sheffield United on 15 December 2007, with a deflected header in the 64th minute of a 1–0 home victory over local rivals Barnsley. He was virtually ever-present in the team in the 2008–09 season, and was voted Sheffield United Player of the Year at the end of the season. Kilgallon started the 2009–10 season as a regular starter once more, but with his contract due to expire the following summer, discussions over a new contract with the club were unsuccessful. At the turn of the year, Kilgallon announced that he intended to see out the remainder of his contract and rejected the opportunity to open transfer talk with Premier League club Burnley.
Sunderland
Kilgallon signed for Premier League club Sunderland on 21 January 2010 on a three-and-a-half-year contract for an undisclosed fee. He made his debut six days later, starting in a 2–0 loss away to Everton. Kilgallon struggled to make an impact during Sunderland's winless run until a man-of-the-match performance against Hull City on 24 April 2010, his first start in months. On 19 August 2010, Kilgallon joined Championship club Middlesbrough on loan for the 2010–11 season. After a man-of-the-match performance at left back against Sheffield United, his loan was cut short by injury. On 12 January 2011, Kilgallon joined another Championship club, Doncaster Rovers, on loan for the rest of the 2010–11 season. After his loan return from Doncaster Rovers, he was not given a squad number for the 2011–12 Premier League. However, after Steve Bruce was dismissed in November 2011, Kilgallon was given a squad number by new manager Martin O'Neill. He returned to the first-team squad as an unused substitute during Sunderland's 2–1 victory over Blackburn Rovers on 11 December 2011. On 1 January 2012, Kilgallon made his first Sunderland appearance since May 2010, coming on as a 26th-minute substitute for the injured Wes Brown against Manchester City. Kilgallon helped keep a clean sheet as Sunderland beat the league leaders 1–0. Two days later, he made his first Sunderland start since May 2010, playing alongside John O'Shea in central defence in a 4–1 away win against Wigan Athletic. He suffered an ankle injury during a 1–0 away defeat against Chelsea on 15 January 2012 and did not reappear until 31 March, starting in an away match against Manchester City. He was substituted in the 81st minute with Sunderland winning 3–1, before the team conceded twice to draw 3–3. During the 2012–13 season, Kilgallon failed to appear in the league until starting in a 0–0 home draw to Queens Park Rangers on 27 November 2012. After playing in Sunderland's 3–0 loss away to Liverpool on 2 January 2013, he did not feature again in the league under Martin O'Neill, but returned to the starting line up for Paolo Di Canio's first match in charge, a 2–1 defeat away to Chelsea, in which scored an own goal. However, this proved to be Kilgallon's last appearance and Sunderland and he was released at the end of the season.
Blackburn Rovers
Kilgallon signed for Championship club Blackburn Rovers on 8 July 2013 on a two-year contract. He made his first start for the club in a 2–1 loss to Wigan Athletic as the captain Scott Dann was injured. Kilgallon signed a new one-year contract at Blackburn in May 2015. He was released at the end of the 2015–16 season.
After his contract was cancelled by mutual consent, Kilgallon signed for Scottish club Hamilton Academical on 31 August 2018. He left Hamilton in May 2019.
Hyderabad FC
Kilgallon signed a deal with Hyderabad FC in 2019 for Indian side Hyderabad FC.
