The early church worried a great deal about heresy. For most of the early Middle Ages no one gave the topic much thought. But starting in the eleventh and twelfth centuries heresy again became an issue for western Christianity, indeed a burning issue by the thirteenth century (forgive the bad pun).
In its simplest form, heresy is a deviant belief by someone who ought to know better, not just a mistake or a misunderstanding, but something clung to in the face of trying to be talked out of it. So Christianity and Islam are not "heresies" to each other, because they are actually different religions (even though they believe in the same God). Heresy was considered dangerous, because the person who rejects the True Faith is certainly going to Hell, and he will take with him anyone he has infected with his false beliefs.
In the early church there were a number of heresies about the relationship between Jesus and God. Was Jesus just an inspired man? Or was he God wearing a human disguise but not human at all? What exactly does the Bible mean when it says that Christ saves? Can we make our own salvation? If we need the sacraments (like baptism) to be saved, what happens if the priest who administers the sacraments is a secret sinner? Most of these questions were never satisfactorily resolved before the rise of Islam in the seventh century, when a predominantly Christian Mediterranean world became predominantly Muslim, and the Christians had other things to worry about than heresy.
The heresies that got western Europe all excited in the twelfth century were different. They were mostly dualist, that is heresies that preached that the universe was the scene of an eternal struggle between absolute good and absolute evil, that neither would win. The physical world belonged to the forces of evil in this heresy, and only the spirit was good.
Now it may at first seem odd that this was a heresy, because Christianity has a lot of dualism in it. But in all orthodox (non-heretical) versions of Christianity, then and now, God is more powerful than the Devil and is going to win eventually, and the material world is God's creation, not the Devil's. In Christian theology, the human will is the source of sin, not the body itself, which is sort of along for the ride.
Dualism became especially prevalent in southern France, where bishops, castellans, whole cities took it up, saying to anyone who would listen that they had finally figured out Christianity's true message. Preachers trying to persuade them differently had no effect. The eventual result in the thirteenth century was a war of northern France against southern France, the "Albigensian Crusade," blessed by the pope, who said that the heresy was a "cancer" that must be "cut out" before it spread further.
Southern France lost the war, and the heretics had to recant or go into hiding. This was the war in which Simon de Montfort, the leader, famously said, when asked if they should massacre a whole town, "Kill them all. The Lord will know His own." It is still not a good idea to tell Simon de Montfort jokes in southern France.
The image above is the castle at Montfort in southern France, named for Simon (the castle has been rebuilt since his day). The fantasy novel Count Scar that I wrote with my husband is a lightly fictionalized version of southern France in the aftermath of the Albigensian Crusade (available as an ebook at http://amzn.com/B0057CVI9S).