Stellar masses play a crucial role in the exploration of galaxy properties and the evolution of the galaxy population. In this paper, we explore the minimum possible uncertainties in stellar mass-to-light (M/L) ratios from the assumed star formation history (SFH) and metallicity distribution, with the goals of providing a minimum set of requirements for observational studies. We use a large Monte Carlo library of SFHs to study as a function of galaxy spectral type and signal-to-noise ratio (S/N) the statistical uncertainties of M/L values using either absorption-line data or broad band colors. The accuracy of M/L estimates can be significantly improved by using metal-sensitive indices in combination with age-sensitive indices, in particular for galaxies with intermediate-age or young stellar populations. While M/L accuracy clearly depends on the spectral S/N ratio, there is no significant gain in improving the S/N much above 50/pix and limiting uncertainties of 0.03 dex are reached. Assuming that dust is accurately corrected or absent and that the redshift is known, color-based M/L estimates are only slightly more uncertain than spectroscopic estimates (at comparable spectroscopic and photometric quality), but are more easily affected by systematic biases. This is the case in particular for galaxies with bursty SFHs (high Hdelta at fixed D4000), the M/L of which cannot be constrained any better than 0.15 dex with any indicators explored here. Finally, we explore the effects of the assumed prior distribution in SFHs and metallicity, finding them to be higher for color-based estimates. ; Comment: accepted for publication on ApJS