Learning dense visual representations without labels is an arduous task andmore so from scene-centric data. We propose to tackle this challenging problemby proposing a Cross-view consistency objective with an Online Clusteringmechanism (CrOC) to discover and segment the semantics of the views. In theabsence of hand-crafted priors, the resulting method is more generalizable anddoes not require a cumbersome pre-processing step. More importantly, theclustering algorithm conjointly operates on the features of both views, therebyelegantly bypassing the issue of content not represented in both views and theambiguous matching of objects from one crop to the other. We demonstrateexcellent performance on linear and unsupervised segmentation transfer tasks onvarious datasets and similarly for video object segmentation. Our code andpre-trained models are publicly available at https://github.com/stegmuel/CrOC.