The abundance of chemical elements across cosmic time provide unique information on the physical processes driving the evolution of galaxies. Current methods for measuring gas-phase metallicities, based on either direct measurements of electron temperature (Te) or calibrations from strong nebular emission line ratios, are based on simplifying assumptions and do not adequately describe the complexity of the emitting regions. We present a new approach based on fitting galaxy spectra with multi-cloud photoionisation models. Unlike current methods, based on comparisons with single-cloud models, our methodology is able to reproduce all observed emission lines to a very high accuracy, down to a few percent, thus allowing for accurate metallicity measurements. We further recover the well known trends between ionization parameter and metallicity, and between the Nitrogen and Oxygen abundances. Our models accurately reproduce the auroral-to-nebular line ratios, while the results of the standard Te method are sometimes very different from the best-fitting model metallity. We finally present newly calibrated metallicity estimators for galaxies based on ratios between strong emission lines.