We investigate here the lithium content of young low-mass stars in the 5~Myr-old star forming region NGC~2264 and its relationship with rotation. We combine lithium equivalent width measurements, EW(Li), from the Gaia-ESO Survey with the determination of rotational periods from the CSI~2264 survey. We consider only bona fide non accreting cluster members in order to minimize uncertainties on EW(Li). We report the existence of a relationship between lithium content and rotation in NGC~2264 at an age of 5~Myr. The Li-rotation connection is seen over a restricted temperature range, Teff=3800--4400K, where fast rotators are Li-rich compared to slow ones. This correlation is similar to, albeit of lower amplitude than, the Li-rotation connection previously reported for K dwarfs in the 125 Myr-old Pleiades cluster. We investigate whether the non-standard pre-main sequence models developed so far to explain the Pleiades results, which are based on episodic accretion, pre-main sequence core-envelope decoupling, and/or radius inflation due to enhanced magnetic activity, can account for an early development of the Li-rotation connection. While radius inflation appears to be the most promising possibility, each of these models has issues. We therefore also discuss external causes that might operate during the first few Myr of pre-main sequence evolution, such as planet engulfment and/or steady disk accretion, as possible candidates for the common origin for Li-excess and fast rotation in young low-mass pre-main sequence stars. The emergence of a connection between lithium content and rotation rate at such an early age as 5~Myr suggests a complex link between accretion processes, early angular momentum evolution, and possibly planet formation, which likely impacts early stellar evolution and still is to be fully deciphered.