DNA methylation at the 5-position of cytosines (5mC) represents an important epigenetic modification involved in tissue differentiation and is frequently altered in cancer. Recent evidence suggests that 5mC can be converted to 5-hydroxymethylcytosine (5hmC) in an enzymatic process involving members of the TET protein family. Such 5hmC modifications are known to be prevalent in DNA of embryonic stem cells and in the brain, but the distribution of 5hmC in the majority of embryonic and adult tissues has not been rigorously explored. Here, we describe an immunohistochemical detection method for 5hmC and the application of this technique to study the distribution of 5hmC in a large set of mouse and human tissues. We found that 5hmC was abundant in the majority of embryonic and adult tissues. Additionally, the level of 5hmC closely tracked with the differentiation state of cells in hierarchically organized tissues. The highest 5hmC levels were observed in terminally differentiated cells, while less differentiated tissue stem/progenitor cell compartments had very low 5hmC levels. Furthermore, 5hmC levels were profoundly reduced in carcinoma of the prostate, breast and colon compared to normal tissues. Our findings suggest a distinct role for 5hmC in tissue differentiation, and provide evidence for its large-scale loss in cancers.