In this paper we explore the clustering properties and the environment of the Extremely Red Objects (EROs; I-K>4mag) detected in a ~180arcmin^2 deep (Ks~20mag) Ks-band survey of a region within the Phoenix Deep Survey, an on-going multiwavelength program aiming to investigate the nature and the evolution of faint radio sources. Using our complete sample of 289 EROs brighter than Ks=20mag we estimate a statistically significant (~3.7sigma) angular correlation function signal with amplitude Aw=8.7^{+2.1}_{-1.7}x10^{-3} consistent with earlier work based on smaller samples. This amplitude suggests a clustering length in the range ro=12-17h^{-1}Mpc, implying that EROs trace regions of enhanced density. Using a novel method we further explore the association of EROs with galaxy overdensities by smoothing the K-band galaxy distribution using the matched filter algorithm of Postman et al. (1996) and then cross-correlating the resulting density maps with the ERO positions. Our analysis provides direct evidence that EROs are associated with overdensities at redshifts z>1. We also exploit the deep radio 1.4GHz data (limiting flux 60microJy) available to explore the association of EROs and faint radio sources and whether the two populations trace similar large scale structures. Cross-correlation of the two samples (after excluding 17EROs with radio counterparts) gives a 2sigma signal only for the sub-sample of high-z radio sources (z>0.6). Although the statistics are poor this suggests that it is the high-z radio sub-sample that traces similar structures with EROs.