Context. Low-mass stars have been recognised as promising targets in the search for rocky, small planets with the potential of supporting life. As a consequence, Doppler search programmes using high-resolution spectrographs like HARPS or HARPS-N are providing huge quantities of optical spectra of M dwarfs. However, determining the stellar parameters of M dwarfs using optical spectra has proven to be challenging. Aims: We aim to calibrate empirical relationships to determine accurate stellar parameters for early-M dwarfs (spectral types M0-M4.5) using the same spectra as those that are used for radial velocity determinations, without the necessity of acquiring IR spectra or relying on atmospheric models and/or photometric calibrations. Methods: Our methodology consists of using ratios of pseudo-equivalent widths of spectral features as a temperature diagnostic, a technique frequently used in solar-type stars. Stars with effective temperatures obtained from interferometric estimates of their radii are used as calibrators. Empirical calibrations for the spectral type are also provided. Combinations of features and ratios of features are used to derive calibrations for the stellar metallicity. Our methods are then applied to a large sample of M dwarfs that are currently being observed in the framework of the HARPS GTO search for extrasolar planets. The derived temperatures and metallicities are used together with photometric estimates of mass, radius, and surface gravity to calibrate empirical relationships for these parameters. Results: A long list of spectral features in the optical spectra of early-M dwarfs was identified. This list shows that the pseudo-equivalent width of roughly 43% of the features is strongly anticorrelated with the effective temperature. The correlation with the stellar metallicity is weaker. A total of 112 temperature sensitive ratios were identified and calibrated over the range 3100-3950 K, providing effective temperatures with typical uncertainties of about 70 K. Eighty-two ratios of pseudo-equivalent widths of features were calibrated to derive spectral types within 0.5 subtypes for stars with spectral types between K7V and M4.5V. We calibrated 696 combinations of the pseudo-equivalent widths of individual features and temperature-sensitive ratios for the stellar metallicity over a metallicity range from -0.54 to +0.24 dex, with estimated uncertainties in the range of 0.07-0.10 dex. We provide our own empirical calibrations for stellar mass, radius, and surface gravity. These parameters depend on the stellar metallicity. For a given effective temperature, lower metallicities predict lower masses and radii as well as higher gravities. Based on data products from observations made with ESO Telescopes at the La Silla Paranal Observatory under programmes ID 072.C-0488(E), 082.C-0718(B), 085.C-0019(A), 180.C-0886(A), 183.C-0437(A), and 191.C-0505(A), as well as data from the Italian Telescopio Nazionale Galileo (TNG) Archive (programmes ID CAT-147, and A27CAT_83).Our computational codes including the full version of Tables 2, 4, and 6 are only available at the CDS via anonymous ftp to http://cdsarc.u-strasbg.fr (ftp://130.79.128.5) or via http://cdsarc.u-strasbg.fr/viz-bin/qcat?J/A+A/577/A132Appendix A is available in electronic form at http://www.aanda.org