Combinatorial representations of point sets play an important role in discrete and computational geometry. In this work, we investigate a new combinatorial quantity of a point set, called Tukey depth histogram. The Tukey depth histogram of k-flats in R^d with respect to a point set P, is a vector D^k,d(P), whose i’th entry Dik,d(P) denotes the number of k-flats spanned by k+ 1 points of P that have Tukey depth i with respect to P. It turns out that several problems in discrete and computational geometry can be phrased in terms of such depth histograms. As our main result, we give a complete characterization of the depth histograms of points, that is, for any dimension d we give a description of all possible histograms D^0,d(P). This then allows us to compute the exact number of different histograms of points.