A new method for the estimation of the intensity distributions of the images prior to normalized mutual information (NMI) based registration is presented. Our method is based on the K-means clustering algorithm as opposed to the generally used equidistant binning method. K-means clustering is a binning method with a variable size for each bin which is adjusted to achieve a natural clustering. Registering clinical MR-CT and MR-PET images with K-means clustering based intensity distribution estimation shows that a significant reduction is computational time without loss of accuracy as compared to the standard equidistant binning based registration is possible. Further inspection shows a reduction in the NMI variance and a reduction in local maxima for K-means clustering based NMI registration as opposed to equidistant binning based NMI registration.