During the Middle Ages , the rest of Europe mostly was Christianized . At that time , Christians were mostly a religious minority in the Middle East , North Africa , and parts of India . During the Middle Ages , most of the remainder of Europe was Christianized , with Christians also being a sometimes large religious minority in the Middle East , North Africa , Ethiopia and parts of India .