Mutual Information (MI) has extensively been used as a measure of similarity or dependence between random variables (or parameters) in different signal and image processing applications. However, MI estimation techniques are known to exhibit a large bias, a high Mean Squared Error (MSE), and can computationally be very costly. In order to overcome these drawbacks, we propose here a novel fast and low MSE histogram-based estimation technique for the computation of entropy and the mutual information. By minimizing the MSE, the estimation avoids the error accumulation problem of traditional methods. We derive an expression for the optimal number of bins to estimate the MI for both continuous and discrete random variables. Experimental results from a speech recognition problem and a computer aided diagnosis problem show the power of the proposed approach in estimating the optimal number of selected features with enhanced classification results compared to existing approaches.