Holy War Before 1095

It is sometimes claimed that the Crusades were the first time warfare was done in the name of religion. While the 11th century saw the defining of The Crusades movement, the concept of religious or holy war go back much earlier. Historian Edward Peter traces the roots of Christian Holy War to the 11th century, but even if was just suddenly formed this late it was because of the need to do so as the Greek East and Latin West were under a new threat of Islam by the aggressive Seljuk Turks.
Further, Constantine claimed to see a Cross in the Heavens as a sign of his coming victory and had used Christianity to further his cause in war against the Western Roman Empire, which had been persecuting Christians for centuries. Many of the Early Christians supported Constantine early in his career for these very reasons.  Charlemagne later fought the Muslims in Spain, a precursor to the later Crusades Movement. The Song of Roland was written long before the Crusades and clearly makes the Christian Muslim conflict a religious issue.  

Some make the claim that while Saint Augustine believed in the doctrine of just war that does not mean he supported ''Holy War..'' In reality, Augustine believed those that didn't hold to the Catholic Faith could be persecuted and he wasn't just talking about war when he said that. Augustine's views though on punishing heretics and his understanding of war will be addressed in another post.
 According to Encyclopedia of The Crusades by Aldfred J. Andrea, there was essentially no difference between just war and Holy War in Medieval Doctrine. Perhaps the main difference between the two in the Medieval Understanding, is the understanding of Salvation and Remission of Sins which follows The Holy War Doctrine. Perhaps Holy Wars were also more rare than wars at large. Church lawyers generally agreed only a pope could summon a Crusade. Between 1095 and 1291 the popes called for seven Crusades. * For more information on the concept of Holy War, read pp. 160-161 of Dr. Andrea's book.

 Emperor Charlemagne fought against the Saxons for many years and infamously in modern times,  slayed four thousand of them and eventually forced the remainders into Christianity. This was centuries before The First Crusade. Charlemagne's favorite book was City of God by Saint Augustine of Hippo which is no surprise given the theocratic influence City of God gave on the Medieval West. The Theology of Forced Christianity and Crusading has been attributed to Saint Augustine of Hippo. Augustine's theology is sometimes considered the end of Ancient Christianity and the beginning of Medieval Christianity.

 Popes had been involved in the political affairs of the Western Christian Empire since at least the Early Middle Ages. Popes ruled the Papal States from the 8th to the 19th centuries. The Monarchy of the papacy in Southern Italy had great influence upon many kingdoms of the west. The role of the church during the Middle Ages is one of the biggest factors of differences between our world and the world of the Medieval West. 5th century Pope Leo I met the Huns and Persuaded them not to invade Rome. It has been said that Emperor Heraclius would have allowed Islam into the Eastern Empire and even wanted harmony between Christianity and Islam but all this was deterred for by Pope Honorious whom opposed the spread of Islam, and sent missionaries throughout the world.  Honorius compared Islam to Arianism, having been aware of Islam just shortly before his death. Monotheltism was an issue of debate still going on in the east and west as Islam was rising as a new religious force. 7th century Pope Donus gave refuge to Eastern monks that fled the Islamic conquest of their homelands. 8th century Pope Gregory III did much to prevent Islam including banning Christians selling other Christians into slavery to the Muslims along with him personally ransoming many Christians from slavery. Gregory III also supported several Christian alliances in war against the Muslims including his support of Charles Martel's defense of France against the Islamic invasion. 8th century Pope Saint Zachary urged the Franks to fight the Muslims.  8th century Pope Gregory III, supported the Franks against the Lombards. 9th century Pope Leo IV even fought in Battle against the Muslims at the Battle of Ostia. The Battle of Civitate was fought between the Normans and those of the papal forces on June 18, 1053. Pope Leo IX had successfully organized a military force against the Normans, only to be defeated. The papacy and the Normans would not become allies until 1059. It has been said that Pope Leo IX was the first Pope to use The Donation of Constantine to his advantage. Islam certainly saw a rise in the Christian belief of Holy War as it never yet. Spain was conquered by Muslims and though Muslim Spain was not entirely hostile to Christians it did kill any Muslim that converted to Christianity. Even Rome was plundered by Muslims in 846 A. D.. Slowly, The Crusades Movement was beginning to rise. Until Urban II, one might be able to argue that most of the previous popes took a more defensive stand towards the west rather than offensive one on the east. This may well be true, but would change when the Byzantines themselves would ask the pope to help them in war against the Seljuk Turks. 

 Several popes had called for Crusades before Urban II including Alexander II and Gregory VII. Much more could be said in detail about these popes and others in their relations to Islam. For more information on this, check the link at the bottom. https://www.thomasmore.org/15-popes-whose-islamophobia-saved-the-christian-world-from-muslim-takeover/
The Donation of Constantine, while now known to be a forgery, was believed to be legitimate by popes for many years. This document claimed that Emperor Constantine gave his power over to the papacy, further legitimizing the politics of popes. Although it had it's skeptics prior, it was believed as a legitimate document until the 15th century.

During the 16th and 17th centuries many Protestants held to a concept of Holy War Including Protestant groups in the Thirty-Years' War and Puritans of the English Civil War. The concept of Holy War among Protestants though is not the subject of this first post which is only about Holy Wars before 1095.
As far as evangelism is concerned, according to Eleanor H. Tejirian and Reeve Spector Simon, after the seventh century evangelism in the West was mostly centered on gaining conversion from the Eastern Church to Islam than to Evangelism of the Middle East. Indeed, the Christian West had quite the time during the Early Middle Ages of converting back various groups in Western Europe from paganism back to Christianity. Islamic rulers refused their subjects being evangelized and the punishments for Muslims converting to Christianity was death. Many Christians were killed under Islamic rule all the while the Islamic countries were free of Missionaries to them from the West. The lack of evangelism towards the Muslim world is also explained by the fact that Bishops often foresaw evangelism in their own diocese, the Roman Church would rather convert multitudes of entire people groups than disperse missionaries to all fronts {which it would later do during The Crusades, by which point all of Europe would then be Christian.} 4th century bishop: Saint Martin of Tours was a bishop and not alone in his efforts to see the destroying of the worship of pagans and replacing it with adoration of the saints and a following of Christianity. Martin of Tours would go on to be venerated throughout the Medieval World.  When it comes to evangelism, no Christian denomination has done more for the world than has the Latin Church in converting Europe and parts of Asia and Africa and America to Christianity. Europe would have not been Christian if it had not been for the evangelism of the Roman Church. Not all of Northern Europe would even come to Christianity until centuries after the origins of Islam  These distractions no doubt, while certainly worthy ones, came as an advantage to the spread of Islam's flame. Further to deter Christian Evangelism of the Middle East, many Muslim conquerors forced Islam on their Christian which became worse and worse as the power of the Seljuk Turks increased. Francis of Assisi however, was willing to die for the Christian faith and would later evangelize unsuccessfully the Muslims during the Fifth Crusade. The great work of Saint Francis was way beyond his homeland in Southern Europe, and his Franciscan order would go on to Evangelize peoples in different parts of the world, even as far as Mongolia. The coming of the Franciscan Order in the 13th century would add another layer to the Medieval Church's outreach to a lost world.
 The Franciscans would be alone as the Dominicans would also be a new order during the Crusades, as would be the Carmelites. The Dominicans, like the Franciscans, would also be great evangelist.
 This is the first post on this topic. More to come!

 *Sometimes Historians list it as 9 Crusades. Hundreds of expeditions happened to the Holy Land during the Middle Ages though not all were officially called upon by the church.
 Further Sources: The Political Writings by Saint Augustine, The Encyclopedia of the Middle Ages by Norman F. Cantor, Encyclopedia of the Crusades by Alfred J. Andrea, Medieval Christianity: A New History by Kevin Madigan, True Christianity: The Catholic Way by John J. Pasquini, Lost History of Christianity by Philip Jenkins, History of the Catholic Church by James Hitchcock, Religion in then Medieval West by Bernard Hamilton, The Western Church in the Middle Ages by John A. Thompson, Conflict, Conquest, and Conversion: Two Thousand Years of Christian Missions in the Middle East by Eleanor H. Tejirian and Reeve Spector Simon.