The evolution of lithium abundance in cool dwarfs provides a unique probe of non-standard processes in stellar evolution. Aims. 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 5Myr. The Li-rotation connection is seen over a restricted temperature range (Teff=800-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 125Myr-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.