born in beverley, humberside, robinson played local sunday league football in the hull boys sunday league. he played in the york city youth system before coming through the youth ranks at leeds united after joining following a trial. he won the fa youth cup with leeds during the 1996–97 season, and kept a clean sheet on his senior debut, a 0–0 draw against chelsea on 25 october 1998.