© 2016 ESO. Context. The evolution of lithium abundance in cool dwarfs provides a unique probe of nonstandard processes in stellar evolution. Aims. We investigate the lithium content of young low-mass stars in the 5 Myr old, star forming region NGC 2264 and its relationship with rotation. Methods. 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 only consider bona fide nonaccreting cluster members to minimize the uncertainties on EW(Li). Results. 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 (T eff = 3800-4400 K), where fast rotators are Li-rich compared to slow rotators. 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 nonstandard 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 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. Conclusions. 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 has yet to be fully deciphered.