Важным видом такой замены стали паломничества в Рим и Иерусалим, а также к могилам Альбана Британского (Сент-Олбанс, Англия) и апостола Иакова Зеведеева (Сантьяго-де-Компостела, Испания). Одной из ранних форм индульгенции являлись «разрешительные грамоты» («litterae remissionis»), которые выдавались в XI–XIII вв. Римскими папами, папскими легатами, правящими епископами и аббатами за пожертвования (на строительство церквей, благотворительных учреждений, школ, мостов, дорог и т.д.) и дела благочестия (например, паломничества). Распространение индульгенций в виде «разрешительных грамот» за пожертвования было во многом обусловлено движением Божьего мира и процессом «внутренней христианизации» Европы. Использовавшиеся в них формулы различались; как правило, употреблялся термин «remissio peccatorum», обозначавший смягчение или снятие епитимии за грехи (в отличие от «absolutio» – отпущения греха в таинстве покаяния). В данных грамотах часто указывались конкретные сроки снятия положенной епитимии, равные срокам покаяния, указанным в «Пенитенциалиях». Впоследствии это привело к возникновению выражений «20 дней индульгенции», «100 дней индульгенции» и т.д., означавших, что с кающегося снимается наказание, соразмерное 20-дневной или 100-дневной епитимии. Позднее подобные грамоты и другие схожие документы слились с грамотами об индульгенции, однако единое богословское и каноническое обоснование такой практики на тот момент ещё не было выработано, что стало причиной её различных толкований и форм, которые нередко отклонялись от позиции Папского престола и впоследствии воспринимались как злоупотребления. Важное место в покаянной практике, которое отводилось совершению паломничеств (в том числе в Иерусалим), повлияло на активное использование индульгенций в Крестовых походах. По мнению исследователей, прототипом папских индульгенций для христианских рыцарей является «разрешительная грамота» (около 1063 г.) папы Римского Александра II, данная сражавшимся с сарацинами в Испании, где провозглашалось снятие епитимии и отпущение грехов «властью святых апостолов Петра и Павла» («nos vero auctoritate sanctorum apostolorum Petri et Pauli et poenitentiam eis levamus et remissionem peccatorum facimus, oratione prosequentes»). Объявляя на Клермонском соборе (1095 г.) о начале похода против сарацин, ставшего первым Крестовым походом, папа Римский Урбан II освободил крестоносцев от всех епитимий, утвердив это вторым каноном Собора: «Путь этот считается за (совершение) всей епитимии» («iter illud pro omni poenitentia reputetur»). Такая практика смягчения покаянной процедуры применялась и впоследствии; например, в каноне  11 Латеранского собора 1123 г. говорится об индульгенции крестоносцам (remissio peccatorum), воевавшим в Святой земле и в Испании.