This paper provides the self-consistent estimator (SCE) and the nonparametric maximum likelihood estimator (NPMLE) for "middle-censored" data, in which a data value becomes unobservable if it falls within a random interval. We provide an algorithm to find the SCE and show that the NPMLE satisfies the self-consistency equation. We find a sufficient condition for the SCE to be concentrated on the uncensored observations. In addition, we find sufficient conditions for the consistency of the SCE and prove that consistency holds for the special case when one of the ends is a constant. Some simulation results and an illustrative example, using Danish melanoma data set, are provided.