We introduce an algorithm to estimate the redshift distribution of a sample of galaxies selected photometrically given a subsample with measured spectroscopic redshifts. The approach uses a non-parametric Voronoi tessellation density estimator to interpolate the galaxy distribution in the redshift and photometric color space. We test the method on a mock dataset with a known color-redshift distribution. We find that the Voronoi tessellation estimator performs well at reconstructing the tails of the redshift distribution of individual galaxies and gives unbiased estimates of the first and second moments. The source code is publicly available at http://bitbucket.org/bengranett/tailz.