O wiele więcej uwagi Konrad poświęcał jednak mocno niepokojącemu go sąsiedztwu Prusów i Jaćwingów. Już w 1206 Konrad sprowadził na Mazowsze z Wielkopolski cystersów, którzy – organizując na trudnym terenie misję – zajęli się szerzeniem religii chrześcijańskiej na tym terenie. W 1212 Konrad spotkał się też w tej sprawie z Leszkiem Białym na synodzie w Mąkolnie, gdzie omawiali z biskupami dalsze plany szerzenia religii chrześcijańskiej wśród sąsiadów. Sukcesy okazały się jednak krótkotrwałe. Niewiele zmieniło się także po ogłoszeniu przez papieża w 1216 – wywodzącego się z cystersów – Chrystiana biskupem misyjnym.

Konrad I w 1217 kazał uwięzić wojewodę mazowieckiego Krystyna, potem wyłupić mu oczy i wreszcie zamordować. Prawdopodobnie wojewoda, będący jednostką wybitną, zanadto „wyrósł” i książę poczuł się zagrożony. Śmierć wojewody Krystyna załamała stworzony przezeń system obrony pogranicza. Napady pruskie powtarzały się odtąd coraz częściej, nękały kraj, stawały się nieznośną zmorą.