In this work, we derive a Monte Carlo expectation maximization algorithm for estimating noise from a noisy utterance. In contrast to earlier approaches, where the distribution of noise was estimated based on a vector Taylor series expansion, we use a combination of importance sampling and Parzen-window density estimation to numerically approximate the occurring integrals with the Monte Carlo method. Experimental results show that the proposed algorithm has superior convergence properties, compared to previous implementations of the EM algorithm. Its application to speech feature enhancement reduced the word error rate by over 30%, on a phone number recognition task recorded in a (real) noisy car environment.