Locke speelde van 1992 tot 2001 voor de Schotse club Heart of Midlothian en verhuisde dan naar de Engelse club Bradford City. Hij keerde na een seizoen al terug naar Schotland en speelde nog voor Kilmarnock FC, in 2009 besloot hij zijn carrière af te sluiten.