Irish defender Sheehan was brought to City after being spotted by a scout whilst playing for the famous Irish club Belvedere FC in 2003. He had to work his way through the ranks to get into the first team, playing regular football for City's U19s side and reserve side, whilst also gaining first team experience with Mansfield Town in 2005, playing ten games for the Stags. He was given a start in City's final game of the 2004-05 season against Plymouth Argyle and was named Academy Player of the Season that year.

He was rewarded with a new two-year contract that would keep him at the club until the summer of 2008, but he never really lived up to his promise as a youngster. Sheehan, who could also play left midfield and had a good left-foot for set-pieces, played just 29 games for the Foxes and scored two competitive goals - one a deflected effort against Watford and the second a more sublime free-kick against old foes Nottingham Forest in a 3-2 win.