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