There is widespread interest in reaching the practical efficiency of cadmium telluride (CdTe) thin-film solar cells, which suffer from open-circuit voltage loss due to high surface recombination velocity and Schottky barrier at the back contact. Here, we focus on back contacts in the superstrate configuration with the goal of finding new materials that can provide improved passivation, electron reflection, and hole transport properties compared to the commonly used material, ZnTe. We performed a computational search among 229 binary and ternary tetrahedrally bonded structures using first-principles methods and transport models to evaluate critical material design criteria, including phase stability, electronic structure, hole transport, band alignments, and p-type dopability. Through this search, we have identified several candidate materials and their alloys (AlAs, AgAlTe2, ZnGeP2, ZnSiAs2, and CuAlTe2) that exhibit promising properties for back contacts. We hope that these new material recommendations and associated guidelines will inspire new directions in hole transport layer design for CdTe solar cells.