Heskey empezó su carrera en el equipo de su ciudad, el Leicester City, hace su debut en liga en el año 1995, frente al Queens Park Rangers, con 14 años.