Neilson's arrival at Leicester, in July 2009, resulted in an historic moment for the club when they travelled to face Ipswich Town at Portman Road the following month - he became the 1000th player to debut for City in a competitive fixture. He arrived from Scottish club Hearts on a three-year deal but he struggled to make the full-back position his own, making 19 appearances in all competitions in his first season with the club.
In his second season, manager Sven-Goran Eriksson saw him as surplus to requirements, as did most of the City faithful, and allowed him to search elsewhere for regular first team football. He ended the campaign on-loan at League One side Brentford and City didn't renew his contract, releasing him in the summer of 2011.