Hendricks was born into poverty in small-town Ohio, the seventh son of a preacher. Starting to sing in church, he learned jazz harmony while still a child from piano legend Art Tatum, a neighbor. Within a few years, during the Great Depression, his singing supported his entire family.