McCary was born as Warner McCary in Natchez, Mississippi, around 1810 or 1811 to an African American slave named Francis, or "Franky", and her master, a whitecarpenter from Pennsylvania named James McCary. They also had two older children, Kitty and Robert. Upon James McCary's death around 1813, his will emancipated Franky and the older children but declared Warner and his future offspring to "be held as slaves during all and each of their lives" in the service of his mother and siblings. In 1836, Warner escaped Natchez on a riverboat and went to New Orleans, where he worked at Leeds Foundry until 1840, as well as an occasional musician and cigar vendor. Around this time he married a white Mormon woman, Lucy Stanton Bassett, who claimed to be a Native American woman named Laah Ceil. She claimed her mother was Delaware Indian and father was Mohawk. In his youth, McCary had begun using other names, including James Warner, William McCary, and Cary. He eventually adopted over a dozen aliases, many of which were Native American, including William Chubbee, William Chubbee King, Julius McCary, William McChubby, Okah Tubee, James Warner, and War'ne'wis Ke'ho'ke Chubbee. Presenting himself as a Native American, McCary was helped in 1843 by local whites to get a permit as a free person of color in Mississippi. When he left in 1844, he toured various frontier and eastern cities as a musician and lecturer. During this time he briefly joined with Mormonism where he sparked racial controversy.
While in Winter Quarters, McCary began claiming powers of prophecy and transfiguration—he claimed to have the power to appear as various biblical and Book of Mormon figures. In early 1847, McCary was excommunicated from the church for apostasy and expelled from Winter Quarters. Shortly after his expulsion, Hyde preached a sermon against McCary and his claims. McCary settled a short distance away and began attracting some Winter Quarters followers to his own brand of Mormonism. He instituted plural marriage among his followers, and had himself sealed to several white wives in a changed, more sexualized sealing ceremony.
McCary's behavior angered many of the Latter Day Saints in Winter Quarters. Researchers have stated that his marriages to his white wives "played an important role in pushing the Mormon leadership into an anti-Black position" and may have prompted Brigham Young to institute the priesthood and temple ordinance ban on black people. A statement from Young to McCary in March 1847 suggested that up until that point, race had nothing to do with priesthood eligibility and the earliest known statement about blacks being restricted from the priesthood from any Mormon leader was made by apostle Parley P. Pratt a month after McCary was expelled from Winter Quarters. Speaking of McCary, Pratt stated that he "was a black man with the blood of Ham in him which linege was cursed as regards the priesthood". After Brigham Young instigated the priesthood and temple ban in 1847, the LDS Church generally did not allow men of black African descent to hold the priesthood again until 1978.
