Topsoil substitute selection is fundamental for the long-term success of reclamation efforts to restore native vegetation to the post-mining landscape in the Appalachian Coal Region. Twenty-nine years of continued research on the Controlled Overburden Placement experiment at the Powell River Project in Wise County, Virginia is used to evaluate the status of soil carbon (C) accumulation and nitrogen (N) retention in reclaimed mine soils under forest and herbaceous vegetation over a gradient of topsoil substitutes. The topsoil substitutes range from pure sandstone (SS) to pure siltstone (SiS) and include ratios of 1:2, 1:1, and 2:1 SS to SiS mixes. Total carbon (TC) and total nitrogen (TN) were determined with dry combustion and soil organic carbon (SOC) with Walkley-Black wet oxidation digestion. Results show that TC, TN, and SOC concentrations increase with increasing SiS under forest vegetation; however, significant differences (p > 0.05) between rock mix types are only present below 5 cm. Total C, TN, and SOC contents were not significantly (p < 0.05) different between rock mix types. Soil OC contents were significantly higher (p > 0.05) under herbaceous vegetation than under forest vegetation for all topsoil substitutes in the surface 25 cm; however, only the SS and 2:1 SS to SiS rock mixes had significantly greater TN contents under herbaceous vegetation. Our results indicate that different topsoil substitutes have different capacities for soil C accumulation and N retention that can be related to vegetative cover.  Choice of overburden rock type may differentially affect the success of revegetation and some ecosystem services (e.g., C sequestration, long-term nutrient availability). Further research will relate soil C and N contents to historic aboveground productivity, overburden weathering rates, and other soil properties.