On 3 May 2004, Gill moved to League Two side Notts County for the 2004–05 season. After a tough start at Meadow Lane, Gill was placed on the transfer list by struggling manager Gary Mills. In November 2004 Mills was replaced by Ian Richardson who immediately removed him from the list. Gill went on to make 57 appearances for the Magpies before being transferred to Conference National side Exeter City on 16 January 2006 during the 2005–06 season, on a free transfer.
