Dzieciństwo i edukacja Jej rodzicami byli wyzwoleni niewolnicy Robert Reed Church i Louisa Ayers, którzy należeli do ciemnoskórej elity Memphis po wojnie secesyjnej. Jej babcia ze strony ojca była Malgaszką, a jej dziadek ze strony ojca, Charles B. Church, białym mężczyzną, właścicielem i operatorem parowca w Wirginii. Przekazał swój majątek synowi, który zainwestował go w nieruchomości i w 1862 zakupił posiadłość w Memphis. Zdobył majątek, skupując nieruchomości, kiedy miasto opustoszało po epidemii żółtej gorączki w 1878. Jest uznawany za pierwszego Afroamerykanina milionera na południu Stanów Zjednoczonych.
Matka Terrell jest uznawana za jedną z pierwszych Afroamerykanek, które miały własny salon fryzjerski. Odwiedzany był przez elity Memphis. Louisa Church odniosła sukces jako przedsiębiorczyni w czasach, kiedy zdecydowana większość kobiet nie miała własnych biznesów. Zachęciła córkę do nauki w Antioch College w Yellow Springs w Ohio, gdzie Mary zdobyła podstawowe i średnie wykształcenie. W wieku lat 12 Mary rozpoczęła naukę w szkole w Oberlin, gdzie uczęszczała też później na studia.
Mary Church Terrell była nazywana przez członków rodziny „Mollie”. Miała jednego rodzonego brata i dwoje przyrodniego rodzeństwa z drugiego małżeństwa jej ojca.