In models of Asymmetric Dark Matter (ADM) the relic density is set by a particle asymmetry in an analogous manner to the baryons. Here we explore the scenario in which ADM decouples from the Standard Model thermal bath during an early period of matter domination. We first present a model independent analysis for a generic ADM candidate with s-wave annihilation cross section with fairly general assumptions regarding the origin of the early matter dominated period. We contrast our results to those from conventional ADM models which assume radiation domination during decoupling. Subsequently, we examine an explicit example of this scenario in the context of an elegant SO(10) implementation of ADM in which the matter dominated era is due to a long lived heavy right-handed neutrino. In the concluding remarks we discuss the prospects for superheavy ADM in this setting.