Weak lensing experiments are a powerful probe of cosmology through their measurement of the mass distribution of the universe. A challenge for this technique is to control systematic errors that occur when measuring the shapes of distant galaxies. In this paper we investigate noise bias, a systematic error that arises from second order noise terms in the shape measurement process. We first derive analytical expressions for the bias of general Maximum Likelihood Estimators (MLEs) in the presence of additive noise. We then find analytical expressions for a simplified toy model in which galaxies are modeled and fitted with a Gaussian with its size as a single free parameter. Even for this very simple case we find a significant effect. We also extend our analysis to a more realistic 6-parameter elliptical Gaussian model. We find that the noise bias is generically of the order of the inverse-squared signal-to-noise ratio (SNR) of the galaxies and is thus of the order of a percent for galaxies of SNR of 10, i.e. comparable to the weak lensing shear signal. This is nearly two orders of magnitude greater than the systematics requirements for future all-sky weak lensing surveys. We discuss possible ways to circumvent this effect, including a calibration method using simulations discussed in an associated paper.