Thanks to its unrivalled sensitivity and large field of view, XMM potentially occupies a leading position as a survey instrument. We present cosmological arguments in favour of a medium-sensitivity, large-scale structure survey with XMM, using galaxy clusters as tracers of the cosmic network. We show how this has motivated the definition of a concrete survey, the XMM Large-Scale Structure Survey (XMM-LSS), which will cover 64 square degrees with a sensitivity about 1000 times better than that of the ROSAT All-Sky Survey. We present our predictions for cluster counts based on the Press-Schechter formalism and detailed X-ray image simulations, and show how they agree with the cluster statistics from recent ROSAT cluster surveys. We also present the extensive multi-wavelength follow-up associated with XMM-LSS, as well as the first observations from the programme.