The distance from a given n×n regular matrix polynomial to a nearest matrix polynomial of normal rank at most r for a specified positive integer r⩽n−1, is considered in two different norm settings. Particular emphasis is given on the distance to nearest singular matrix polynomials. The problem is shown to be equivalent to computing smallest structure preserving perturbations such that certain convolution matrices associated with the matrix polynomial become suitably rank deficient. In particular, the distance to singularity is seen to be equivalent to the rank deficiency of two different types of block Toeplitz matrices. This leads to new characterizations of the distance. Upper and lower bounds as well as information about the minimal indices of nearest singular matrix polynomials follow from these characterizations. The distances are also established to be reciprocals of certain generalized structured singular values, thus showing that computing the distance to singularity may be an NP hard problem. Based on the results, a strategy to compute the distance to singularity is devised and implemented via numerical algorithm based on BFGS and Matlab's globalsearch.m. Numerical experiments show that the computed distances compare favourably with values obtained in the literature and the bounds are tight.