The Large Early Galaxy Census (LEGA-C) is a Public Spectroscopic Survey of $\sim3200$ $K$-band selected galaxies at redshifts $z=0.6-1.0$ with stellar masses M_star > 1e10M_sun, conducted with VIMOS on ESO's Very Large Telescope. The survey is embedded in the COSMOS field ($R.A. = 10h00$; $Dec.=+2\deg$). The 20-hour long integrations produce high-$S/N$ continuum spectra that reveal ages, metallicities and velocity dispersions of the stellar populations. LEGA-C's unique combination of sample size and depth will enable us for the first time to map the stellar content at large look-back time, across galaxies of different types and star-formation activity. Observations started in December 2014 and are planned to be completed by mid 2018, with early data releases of the spectra and value-added products. In this paper we present the science case, the observing strategy, an overview of the data reduction process and data products, and a first look at the relationship between galaxy structure and spectral properties, as it existed 7 Gyr ago.