Didn't slavery initially have a religious justification? I know the Portuguese brought Black Africans back to Europe as slaves on the grounds that they were Muslims and therefore deserved it.
While the Portuguese got a lot of Muslim slaves, especially during the 15th and 16th Centuries, most of their slaves weren't Muslim, and came from what is now Angola and Mozambique (at least in Brazil, where they needed huge amounts of slaves to work in the plantations, and later in the gold mines). The justification for slavery came from a more vague notion that black people had no souls, and therefore there were little to no ethical concerns regarding them. The fact that many of the slaves that the Portuguese bought were criminals certainly didn't reduce these beliefs, either.
EDIT: Note that the Portuguese didn't always religiously or racially justify slavery - Amerindians were often enslaved in Brazil, even though the Jesuits preached that Native Americans were pure and innocent beings, like children.