Although the Ceratopsia and Pachycephalosauria, two major ornithischian groups, are united as the Marginocephalia, few synapomorphies have been identified due to their highly specialized body-plans. Several studies have linked the Heterodontosauridae with either the Ceratopsia or Marginocephalia, but evidence for these relationships is weak, leading most recent studies to consider the Heterodontosauridae as the basal member of another major ornithischian radiation, the Ornithopoda. Here, we report on a new basal ceratopsian dinosaur, Yinlong downsi gen. et. sp. nov. from the Late Jurassic upper part of the Shishugou Formation of Xinjiang, China. This new ceratopsian displays a series of features transitional between more derived ceratopsians and other ornithischians, shares numerous derived similarities with both the heterodontosaurids and pachycephalosaurians and provides strong evidence supporting a monophyletic Marginocephalia and its close relationship to the Heterodontosauridae. Character distributions along the marginocephalian lineage reveal that, compared to the bipedal Pachycephalosauria, which retained a primitive post-cranial body-plan, the dominantly quadrupedal ceratopsians lost many marginocephalian features and evolved their own characters early in their evolution.