Stalni napadi na Bosnu zbog njene duhovne „hereze“ teku u vrijeme krstaških ratova (1096–1270), koji su veoma produbili vjerski fanatizam i netoleranciju, kako na zapadu, tako i na istoku Evrope. Uz sve svoje poslove vezano za organiziranje velikih križarskih pohoda na Istok rimske pape, ugarsko-hrvatski kraljevi i velikaši neprekidno rade na konačnom uništenju „bosanske hereze“, a ustvari bosanske države i njene samostalnosti.
Tri decenije, od sabora na Bilinom polju do dolaska na vlast bana Mateja Ninoslava 1232. godine, obilježene su u Bosni jačanjem i širenjem onoga što u Rimu vide kao „herezu“, te naglim porastom moći i utjecaja bosanske vlastele. U tom se vremenu „hereza“ iz Bosne proširila na susjednu Slavoniju, a bosanski krstjani su stupili u neposredne veze s „hereticima“ u Italiji i južnoj Francuskoj. Iz akta o odricanju vidi se da su bosanski krstjani u vrijeme sabora na Bilinom polju imali svoje starješine, a to znači i vjersku organizaciju. U latinskim se izvorima za nju redovno koristio naziv ecclesia Sclavoniae i u pravilu se odnosio na Bosnu i Crkvu bosansku. Bosansko-slavenski termin Crkva bosanska prvi put spominje se u jednoj povelji bana Stjepana II Kotromanića, koja vjerovatno potiče iz 1325.
Od 1221. u brojnim se papskim pismima konstatira da su „heretici u bosanskim krajevima“ ponovo ojačali i da imaju podršku ne samo u narodu nego i među vlastelom i slavenskim svećenstvom službene katoličke crkve. U Rimu je zato odlučeno da se neće, kao 1203, ići na ispitivanje i pridobijanje heretika nego na njihovo iskorjenjivanje silom. Papa se radi toga obratio kralju, plemstvu i svećenstvu Ugarske da rade na prikupljanju i pridobijanju krstaša za pohod na Bosnu. Ugarsko-hrvatski kralj Andrija II ovlastio je 1225. nadbiskupa da Bosnu, Usoru i Soli „čisti“ od heretika. Mada je kaločki nadbiskup „rabro pripasao krstaški mač“, nije u to vrijeme uspio organizirati ni prikupiti vojsku za pohod protiv Bosne.
Papa je 1233. uputio u Bosnu svog novog izaslanika, kardinala Jakoba. On je tu zatekao novog bana Mateja Ninoslava, koga je privolio da skupa sa svojim rođakom Prijezdom pređe na katoličanstvo. Prof. dr. Mustafa Imamović je u svojim istraživanjima ocijenio da bana Ninoslava nije toliko interesiralo pitanje hereze, koliko činjenica da se u to vrijeme vlastela u velikoj mjeri otrgla vladarevoj neposrednoj vlasti. Bosanski velikaši nastoje da župe kojima su do tada upravljali kao vladarevi službenici pretvore u svoje feude. Ban se 1233. žali papi Grguru IX da se njegova vlastela ne pokorava, prema starom običaju, njegovoj vrhovnoj vlasti, nego povjerenim župama samostalno upravljaju. On se posebno žali što se njemu, „oji je nedavno sa heretičke prešao na katoličku vjer“, uskraćuju prava koja se njegovi preci uživali, povjeravajući i oduzimajući sela i župe kome su htjeli i kako su sami nalazili potrebnim. Papa je na to ovlastio hercega Hrvatske Kolomana, sina ugarskog kralja, da preduzme akciju kako bi se u Bosni održao „tari običa“, jer bi to bilo, „a korist vjere a na propast heretičke opačin“.
Herceg Koloman se spremno stavio na čelo krstaške akcije kojom je namjeravao u svoju korist ukloniti domaću bosansku dinastiju. Time se jasno pokazalo da je „bosanska hereza“ u prvom redu političko, a ne vjersko pitanje. Krstaški pohod na Bosnu počeo je 1235. i s prekidima je trajao tri godine. Na čelo otpora krstašima odmah se bez oklijevanja stavio ban Matej Ninoslav. On je u otporu ugarsko-hrvatskoj krstaškoj vojsci uspio ujediniti sve strukture bosanske države, domaću vlastelu i crkvu, te posebno seljaštvo. Ban se nije osvrtao na optužbe iz Rima da je ponovo otpao od katoličke crkve. Krstaška vojska je uspjela uz mnogo prolivene krvi proći kroz Bosnu i Humsku zemlju, ali se s opljačkanim plijenom morala 1238. povući. Nakon toga, stvari su u Bosni opet krenule svojim uobičajenim tokom.
Položaj bana Matije Ninoslava posebno je ojačan 1241/42, kada je u velikoj mongolskoj najezdi opustošeno ugarsko-hrvatsko kraljevstvo sve od Erdelja do zidina dalmatinskih gradova. U metežu koji je potom nastao Split je bana Ninoslava izabrao za svog kneza, jer je svojom oružanom intervencijom omogućio Splićanima da poraze kralju odani Trogir. Smatrajući da su ovom intervencijom povrijeđena njegova suverena prava nad dalmatinskim gradovima, kralj Bela IV je 1244. poveo novi rat protiv Bosne.
Ban Ninoslav je izbjegao rat pristankom da se bosanskoj katoličkoj biskupiji ponovo potvrde prava i privilegije koje je formalno uživala još od sabora na Bilinom polju. Kako je još papin izaslanik kardinal Jakob deset godina ranije optužio dubrovačkog nadbiskupa, čijoj je mitropoliji pripadala Bosna, da ništa ne poduzima protiv bosanskih heretika, to su crkveni poslovi u Bosni ponovo stavljeni pod jurisdikciju kaločkog nadbiskupa. On je odmah u sjevernim krajevima Bosne podigao više tvrđava radi odbrane i zaštite vjere i crkve. Pod stalnim napadima domaće vlastele i stanovništva, te su tvrđave postepeno napuštene i sasvim propale.
Tako se upravo u vrijeme bana Mateja Ninoslava, koji se pred brojnim vanjskim pritiscima i opasnostima iskazao kao odlučan i sposoban vladar, konačno uobličila i učvrstila društvena i politička struktura bosanske države. Učvršćena je staleška organizacija bosanske vlastele i struktura Crkve bosanske. Pred brojnim vanjskim neprijateljima vlastela i crkva su se sve više međusobno približavali.
Vlastela se držala učenja Crkve bosanske, dok je Crkva bosanska sve više ulazila u svjetovne poslove i političke odnose vlastele i države. U tom međusobnom savezu branila se od nasrtaja rimske crkve i okolnih država, kako vjerska, tako i politička samobitnost i samostalnost Bosne. Uvjet opstanka i crkve i vlastele bila je samostalnost bosanske države. Samo na taj način i crkva i vlastela mogli su izbjeći političku marginalizaciju i potčinjavanje, bilo Zapadu, bilo Istoku.
Posljednji spomen velikog bosanskog bana Mateja Ninoslava potječe iz 1249. godine. Poslije toga, ugarski kralj Bela IV je odlučnom vojnom akcijom 1253. praktično savladao otpor u Bosni, ali „herezu“ nije uspio ozbiljnije ugroziti.
