This study was designed to evaluate the effectiveness of subepithelial connective tissue graft (SCTG) and acellular dermal matrix allograft (ADMA) in root coverage procedures and to examine the effect of interdental papilla dimensions on the outcome of root coverage using a new approach. This randomized controlled clinical study included 32 gingival recession defects of at least 2 mm classified as Miller Class I or II. Clinical parameters were measured at baseline and 6, 12, and 24 weeks postsurgery. At baseline, all measured clinical parameters were statistically equivalent between the two groups. With regard to the amount of mean root coverage, no significant difference was found between ADMA (85.42%) and SCTG (69.05%) groups. However, the percentage of complete root coverage was significantly greater in the ADMA group (75.0%, versus 31.3% in the SCTG group). Significant positive correlations were found between papilla height and papilla width and mean root coverage, and papilla height of at least 5 mm was associated with complete root coverage. ADMA seems to be a good substitute for SCTG to treat shallow to moderate gingival recessions. In addition, papilla dimensions, as measured using the new method, can help predict the success of future root coverage.