Реформы XI столетия значительно усилили папство. Папа Лев IX в середине века возглавил поход против нормандцев в южной Италии, называя их язычниками за их жестокость, и обещал немецким участникам похода отпущение грехов. Папа Николай II заключил в Мельфи в 1059 г. союз с вождем итальянских нормандцев Робером Гискаром. Тот согласился получить свои владения от папы в виде лена и стал, таким образом, папским вассалом. Папство получило в свое распоряжение ленную армию для ведения священных войн. Эти же нормандцы с согласия церкви осуществили в виде священной войны с неверными отвоевание у арабов Сицилии (1061-1072 гг.). Благословение церкви и освященное папой знамя получил нормандский герцог Вильгельм при завоевании Англии (1066) у «клятвопреступника» — англосакского короля Гарольда. В Испании под покровительством папства и при активном участии французов продолжалась священная война с неверными. Папа Александр II поддержал поход, направленный на завоевание Барбастро (Арагон) в 1064 г., и даровал отпущение грехов его участникам. В мае 1085 г. король Кастилии и Леона Альфонс VI овладел Толедо, древней столицей вестготских королей, и провозгласил себя императором. После этого испанские эмиры призвали Альморавидов из Африки, нанесших в 1086 г. жестокое поражение императору Альфонсу. Папы многократно призывали французское дворянство на помощь испанским христианским государствам и отпускали грехи участникам борьбы с неверными. Борьба с мусульманами считалась очень почетной, и опыт привлечения французской помощи испанцам был удачным, несмотря на отсутствие крупных побед у христиан. Испанские войны, без сомнения, оказали большое влияние на возникновение идеи крестовых походов. Помимо этого, пребывая на юге Италии, папа Урбан II, несомненно, обратил внимание на войну итальянских нормандцев с арабами, а также на экспедицию пизанского и генуэзского флотов в 1087 г. против Туниса, в которой участвовали пизанцы, ранее совершившие паломничество в Рим и имевшие кроме оружия еще посохи и котомки паломников.
Мирные паломничества европейских христиан к Святым местам начались задолго до крестовых походов. Иерусалим стал местом паломничества с тех пор, как святая Елена нашла вблизи него Святой Крест, на котором был распят Христос, и Камень Помазания, куда возложили снятого с Креста Иисуса, а ее сын, император Константин, воздвиг комплекс церковных зданий Гроба Господня на месте Его казни. В начальный период существования ислам отличался терпимостью, и мусульмане сохранили часть церквей на землях, отнятых у христиан, разрешали богослужение и не препятствовали паломникам. Карл Великий, обменявшийся несколькими посольствами с халифом Аббасидом Харун ар-Ратидом, посылал в начале IX в. деньги на восстановление и строительство новых церквей и монастырей в Палестине. С тех пор всех западных европейцев латинского обряда, вне зависимости от происхождения, на Ближнем Востоке стали звать франками. В Западной Европе твердо знали, что мусульмане овладели Святой Землей насильственно и христиане имеют неотъемлемое право на Иерусалим, а также серьезно верили легенде, что Карл Великий совершил туда паломничество.
При Фатимидах, овладевших Палестиной во второй половине X в., терпимое отношение к христианам не изменилось. Однако при халифе аль-Хакиме, «жестоком фанатике и яростном безумце», в начале XI в. начались гонения на христиан. Он приказал разрушить церковь Гроба Господня в Иерусалиме, объясняя это тем, что чудо схождения Благодатного Огня в Страстную субботу перед Пасхой является безбожным обманом.
Полоса терпимости, наступившая после его смерти, увеличила число паломников, а византийские императоры начали восстанавливать разрушенную церковь Гроба Господня. Восстановление было завершено императором Константином Мономахом в 1046 г., христианский квартал Иерусалима, так же как церковные здания при Гробе Господнем, был огражден каменной стеной. Однако после раскола христианской церкви византийские чиновники стали облагать налогом паломников с Запада, возможно, по требованию императора, им было запрещено входить в церковь Гроба Господня, и более трехсот католиков в 1056 г. были выселены из Иерусалима. Однако вскоре ограничения были сняты, и до последнего десятилетия XI в. количество паломников с Запада непрерывно росло.