Mutual information is a widely used similarity measure for aligning multimodal medical images. At its core it relies on the computation of a discrete joint histogram, which itself requires image samples for its estimation. In this paper we study the influence of the sampling process. We show that quasi-random sampling based on Halton sequences outperforms methods based on regular sampling or on random sampling. Our results suggest that sampling itselfand not interpolation, as was previously believed is the source of two major problems associated with mutual information: the grid effect, whereby grid-aligning transformations are favored, and the overlap problem, whereby the similarity measure exhibits discontinuities. Both defects tend to impede the accuracy of registration; they also result in reduced robustness because of the presence of local optima. By estimating the joint histogram by quasi-random sampling, we solve both issues at the same time.