Denisovans are a human group unique for having been described solely based on ancient DNA analysis. Whereas the genome of this group is sequenced to high-coverage, the paucity of paleontological remains makes their morphology virtually unknown. Based on DNA sequence alone, very limited inference on their appearance was offered. We present a method to reconstruct anatomical features based on comparison of DNA methylation maps between Denisovans and modern humans. From these comparisons we predict changes in expression levels of genes, and intersect them with anatomical changes using known phenotypic consequences of loss-of-function mutations. We then combine evidence from all genes associated with a trait, and show that this increases prediction power threefold. We test the performance of our method by using it to predict anatomical features of the Neanderthal and the chimpanzee, and compare them to their known morphology. We show that we reach ~84% accuracy in identifying diverged traits and ~82% in predicting their direction of change. We then reconstruct an anatomical profile of the Denisovan, and show that this group likely shared many traits with Neanderthals, including a projecting face, robust jaws, low forehead and wide pelvis. We also identify additional changes along the Denisovan lineage, such as biparietal expansion of the cranium, and a change in the length of the tooth arch. Finally, we find that most of the morphologies identified in the Xuchang crania, which were speculated to belong to Denisovans, are predicted by our methylation-based anatomical profile, providing further support to their identification as Denisovans.