Interval censored data arises when individuals can be subjected to periodic inspection at possibly random moments, and their status (e.g. failed or functioning) is ascertained at each inspection. We exploit the order theoretic properties of interval orders to develop a new language describing interval censored data. We show that inference can be based on the set M of maximal antichains of the data, rather than on the real line, extending the reasoning of Turnbull (1976). We show how M can be used to obtain the nonparametric maximum likelihood estimators suggested by Turnbull (1976). We discuss some properties of self-consistent estimators of the cumulative distribution function in light of the structure of M. We show the identity between self-consistency augmented by Kuhn-Tucker conditions and Fenchel duality, which characterize the NPMLE on M. We port to M recently developed isotonic regression techniques to estimate the NPMLE (Wellner & Zhan, 1997). Keywords: interval censored data,...