Swoją karierę piłkarską rozpoczynał w roku 1996 w juniorskim zespole Wolverhampton Wanderers. Do pierwszej kadry został włączony rok później. W trakcie dziewięcioletniego pobytu w tej drużynie wystąpił niemal w 300 spotkaniach, w których zdobył siedem bramek. W roku 2006 podpisał kontrakt z Celticiem. W drużynie tej Naylor jest jednym z podstawowych zawodników i zaliczył już ponad 80 występów w lidze, w których zdobył dwie bramki.

W latach 2000–2001 Naylor wystąpił w trzech meczach reprezentacji Anglii do lat 21