The Universe is comprised of hundreds of billions of galaxies, each populated by hundreds of billions of stars. Astrophysics aims to understand the complexity of this almost incommensurable number of stars, stellar clusters and galaxies, including their spatial distribution, formation, and current interactions with the interstellar and intergalactic media. A considerable fraction of astrophysical discoveries require large statistical samples, which can only be addressed with multi-object spectrographs (MOS). Here we introduce the MOSAIC study of an optical/near-infrared MOS for the European Extremely Large Telescope (E-ELT), which has capabilities specified by science cases ranging from stellar physics and exoplanet studies to galaxy evolution and cosmology. Recent studies of critical technical issues such as sky-background subtraction and multi-object adaptive optics (MOAO) have demonstrated that such a MOS is feasible with current technology and techniques. In the 2020s the E-ELT will become the world’s largest optical/IR telescope, and we argue that it has to be equipped as soon as possible with a MOS. MOSAIC will provide a vast discovery space, enabled by a multiplex of ∼ 200 and spectral resolving powers of R = 5 000 and 20 000. MOSAIC will also offer the unique capability of 10-to-20 ‘high-definition’ (MOAO) integral-field units, optimised to investigate the physics of the sources of reionisation, providing the most efficient follow-up of observations with the James Webb Space Telescope (JWST). The combination of these modes will enable the study of the mass-assembly history of galaxies over cosmic time, including high-redshift dwarf galaxies and studies of the distribution of the intergalactic medium. It will also provide spectroscopy of resolved stars in external galaxies at unprecedented distances, from the outskirts of the Local Group for main-sequence stars, to a significant volume of the local Universe, including nearby galaxy clusters, for luminous red supergiants.