Before Martin Luther hung his 95 Theses on the door of the Wittenberg Castle church in 1517, Europe had been Catholic since the first century, and all of the popes (St. Peter was the first) from 741 to 2013 were from Europe. With the clergy, especially those ranked under the pope, the cardinals, wielding tremendous political power--the clergy were the Second Estate in medieval France, for instance--the Catholic Church was extremely influential in European government. In fact, the Pope was, indeed, also the king in Italy, and, therefore, puissant. [And, for a time, the Pope was seated in France: in 1305 in Poitiers, and then in 1309 the Papal Seat was in Avignon. At that time with the powerful Catholic Church's head located in France, the power of the French king was uncontested.]
The dates mentioned in this question nearly coincide with the dates of the Crusades (1095-1291); during this time, of course, Christianity was a mighty force. After the Byzantine Empire (formerly the Eastern part of the Roman Empire) began to lose territory to invading Turks. The Christian ruler, Alexis I, sent envoys to Pope Urban II requesting military troops from the West to aid in repulsing the Turkish threat. When the Muslims invaded Jerusalem, Pope Urban II at the Council of Clermont in 1095 urged European Christians to reclaim the territory from those considered "infidels" at that time. With all of Europe's Christians united in this Holy War, then, the papacy became pre-eminent as the leader of the Christian world which waged, according to historians, seven major crusades and sever minor ones. All the European countries answered to the pope, until Henry VIII broke from the Catholic Church when the pope would not annul his marriage so he can Anne Bolelyn.
Also, during the Middle Ages (1154-1485) the Catholic Church was both the religious and cultural center of people's lives. Massive cathedrals were constructed during this time, and it was around the church that festivals and various cultural, religious, and some political activities were conducted. (One is reminded of the Festival of Fools in Victor Hugo's novel, Notre-Dame de Paris, also called The Hunchback of Notre Dame) in which poor Quasimodo is made the "King of Fools" and locked in the stocks for people to mock.