Джованни прибыл в Монпелье осенью 1200 года, но его деятельность в Лангедоке не оставила следов, и он поспешил вернулся в Рим в следующем году.

Затем последовали три года бездействия, в течение которых южное дворянство предсказуемо не откликнулась на обещание индульгенций от Рима за изгнание еретиков из их земель. Только летом 1203 года Иннокентий нашел в лице Пьера де Кастельно легата, способного решить эту проблему. Пьер был монахом аббатства Фонфруад, расположенного недалеко от Нарбона. Он был богословом и каноническим юристом, способным и энергичным, но со всей узостью взглядов, которую предполагало его происхождение. Он был цистерцианцем, как и все его предшественники, но в отличие от них у него было преимущество — он был человеком с Юга, родившимся в плоской, поросшей виноградом стране к северу от Монпелье, которая на протяжении всей его жизни оставалась оплотом католицизма на Юге. Другой монах из Фонфруада, некто Ральф, получил назначение вместе с Пьером в качестве солегата, но он редко выходил из тени своего властного коллеги. Более мощное подкрепление пришло в следующем году с назначением третьего легата, Арно-Амори, аббата Сито. Арно-Амори также был южанином и до избрания на высший пост своего ордена был аббатом Грансельве и филиала Фонфруада в Поблете, Каталония. Из всех церковников, участвовавших в Альбигойском крестовом походе, Арно-Амори был ближе всего к фанатизму. Ему было сподручнее вести 40.000 человек на поле битвы при Лас-Навас-де-Толоса, чем заниматься тяжелой, часто не приносящей удовлетворения работой по обращению катаров. Сдержанность, которую налагал на него статус легата и священника, стесняла его. Иннокентий поручил ему миссию, и он сделал все возможное, чтобы ее выполнить. Но сердце его не лежало к этому, пока крестовый поход не предоставил ему возможность для решительных действий, которые пришлись ему по вкусу. "Убейте их всех; Бог узнает своих", — возможно, Арно-Амори не произносил эту фразу, но она полностью раскрывает характер человека, который больше, чем Святой Доминик, заслуживает звания отца инквизиции.

Легаты Иннокентия были наделены абсолютной властью. Юрисдикция епископов на искоренения ереси была передана им; они были уполномочены добиваться своего путем отлучения и интердикта; любого церковника, который казался им препятствующим или недостойным своей должности, они могли сместить без уведомления и права на апелляцию. Эти всеобъемлющие полномочия не способствовали расположению легатов к местному духовенству и, вполне возможно, оказались скорее помехой, чем подспорьем. Архиепископ Нарбонский жаловался, что легаты вели себя грубо и бесцеремонно, не уведомляя его о своем присутствии в его епархии в соответствии с принятыми нормами вежливости и давая ему императивные указания, как будто он был простым аколитом. Он отказался сопровождать их к Раймунду VI и даже предоставить им вооруженный эскорт. С некоторым трудом им удалось убедить архиепископа выделить одного рыцаря для охраны в пути. Епископ Безье и избранный епископ Магелона были столь же непреклонны в своем отказе сопровождать папских легатов. Однако в Тулузе, куда легаты добрались со своим небольшим эскортом в декабре 1204 года, теплый прием опроверг репутацию города как "ядовитого гнезда ереси". Епископа, аббата Сен-Сернин и консулов убедили поклясться, что они не потерпят еретиков в своих владениях. В обмен на это были подтверждены их привилегии, и это было бесцеремонным присвоение власти, которое, должно быть, раздражало графа не меньше, чем епископа. Жители Безье, возможно, менее ортодоксальные или менее поддающиеся на взятки, отказались принести подобную клятву; епископ не согласился заставить их сделать это, пока ему не пригрозили отлучением в присутствии подчиненного ему духовенства.

Трех месяцев легатства хватило, чтобы убедить Пьера де Кастельно, что в первую очередь начинать надо с епископов Лангедока. Епископ Безье был немедленно лишен сана и заменен администратором. Епископ Вивье был отстранен от должности после того, как его каноники обвинили его в различных злоупотреблениях, и был бы смещен, если бы не принадлежал к влиятельной семье. Даже аристократические связи не спасли епископа Тулузы Раймунда де Рабастана, который был вынужден уйти в отставку после того, как стало известно, что он подкупал своих избирателей и распродавал имущество епископства для финансирования личной войны. Дело Беренгера, архиепископа Нарбонского, требовало большей осмотрительности. Низложение архиепископа было серьезным делом, особенно если он был дядей короля Арагона, в котором Иннокентий уже видел лидера возможного крестового похода. Беренгер, по которому папская курия не принимала решений, оставался архиепископом Нарбона до 1212 года. К этому времени, однако, почти никто из его коллег не занимал постов, которые они занимали по прибытии Пьера, девятью годами ранее.

В 1204 году Педро II Арагонский был для легатов особенно важен. Обладание обширными, хотя и несколько номинальными феодальными правами в Лангедоке делало Педро приемлемой заменой графу Тулузскому, который не хотел с ними сотрудничать. В феврале 1204 года он председательствовал на официальных дебатах в Каркассоне, в которых участвовали представители и вальденсов, и катаров. Это было драматическое событие, и для легатов оно стало откровением о масштабах их проблем. Но неизбежное отлучение еретиков от Церкви не имело смысла. Давно прошло то время, когда можно было добиться обращения в христианство, просто указав на то, что катары не обладают авторитетом Церкви. Подводя итоги своих достижений в конце первого года деятельности легатом, Пьер де Кастельно признал, что они были весьма незначительны. Он начал испытывать ту ностальгию по тихой монастырской жизни, которой поддавались предыдущие легаты, и ему требовалось напоминание своего далекого начальника о том, что "вера сияет в невзгодах… и усилия так же угодны Господу, как и достижения". Sursum corda (Укрепите свои сердца).

Сам Иннокентий уже думал о другом. Узнав, что катары захватили Лескюр, собственность Святого Престола, он предложил город в качестве фьефа Педро II Арагонскому, если тот сможет его взять. Педро, всегда стремившийся получить реальную власть к несколько неопределенным правам, которыми он уже обладал в западном Лангедоке, захватил город в начале следующего года. С другими своими поборниках Папа был менее удачлив. Он уже однажды писал королю Франции Филиппу II Августу о распространении ереси в южной части его королевства. В феврале 1205 года, через две недели после обнадеживающего письма легатам, Иннокентий вновь обратился к номинальному сюзерену Раймунда, умоляя его вмешаться в дела Юга или хотя бы послать для этого своего сына. Однако Филипп был озабочен планами вторжения в Англию, а его армия располагалась под стенами Лоша и Шинона. Ответ короля не сохранился, но вряд ли он был обнадеживающим. Однако растущие свидетельства папского негодования начали тревожить Раймунда VI. Летом 1205 года он решил успокоить легатов, дав клятву изгнать еретиков из своих владений. Это было обещание, которое как он знал, не в состоянии был выполнить, но которое легаты не забыли.

К концу июньского дня 1206 года случайная встреча у восточных ворот Монпелье изменила направление миссии Пьера. Два кастильца,