Iako smo u prošlom članku o banu Kuliniću naveli da je on svrgnut 1232. godine i da je na njegovo mjesto postavljen novi ban Matej Ninoslav, postoje određene indicije da je novi ban još i ranije došao na bansku stolicu. Nakon što su propali svi pokušaju koje je poduzeo Andrijin nećak, carević Ivan, u nastojanju da se savladaju heretici u Bosni, bosanski bogumili 1227. godine skinuše bana Stjepana i na bosansku stolicu podigoše svog čovjeka, rođenog i odgojenog heretika, Mateja Ninoslava. Nemamo puno podataka o njemu osim da mu se otac zvao Radivoj a brat Simeon. Ban Matej Ninoslav je daleko znamenitija ličnost u srednjovjekovnoj bosanskoj historiji od njegovog prethodnika. Ipak, kako je iz Rima i Ugarske vršena strahovita propaganda protiv novog vladara, on 1233. godine popusti papskom poslaniku Jakobu i primi kršćanstvo, ali samo iz razloga da se spriječi krvoproliće po Bosni. Na kršćanstvo je prešao i njegov rođak Prijezda. Treba naglasiti da je u brojnim papinskim pismima Ninoslav etiketiran kao “veliki ban”, a njegov rođak Prijezda samo kao “ban”. Međutim, ovakav “uspjeh” Rima i Ugarske nije bio dugog vijeka. Već naredne godine u Bosni je ponovo došlo do sve očitijeg ispoljavanja bogumilske vjere, koja se širila i na susjednu Hrvatsku. U jednom pismu papa opisuje Bosnu kao “pustinju i šikaru, punu trnja i kopriva i postala je leglo guja (heretika)”. Obzirom da je Bosni prijetio križarski rat ban je nastojao popustiti papi kako bi se izbjeglo krvoproliće. Međutim, novi biskup ne samo da je imenovan uz podršku bosanskih bogumila, već ni same crkvene obrede nije znao izvršavati po kršćanskim načelima, niti je iskrivljene obrede vršio na latinskom jeziku. Takvo stanje je željela iskoristiti susjedna Ugarska, koja je imala pretenzije na Bosnu. Kako bi ponizio novog bosanskog bana, ugarski kralj Andrija Bosnu poklanja hercegu Kolomanu 1234. godine. Time je dovedena samostalnog Bosne u pitanje ali i vlast bana Ninoslava. Istovremeno je to ohrabrilo i kneza Sibislava (sina od bivšeg bana Stjepana) da počne sa napadima na dijelove Bosne kojima je vladao Ninoslav, pokušavajući time da preuzme bansku vlast. Svi ovi poduhvati jasan su pokazatelj taktičkog prihvatanja kršćanstva, ali ipak samostalnost Bosne je i dalje ugrožavana.
Težak položaj Bosne iskorištava i papa Grgur IX i 1235. godine (po nekim izvorima 1234) pokreće križarski rat protiv Bosne. Andrija II predaje svome sinu Kolomanu upravu nad cijelom Bosnom. Time je jasno bilo i banu Ninoslavu da se Bosni sprema velika invazije kršćanske vojske. Ban je napustio kršćanstvo, koje je i onako zbog interesa prihvatio, te pozvao bosanski narod na otpor protiv Rima i Ugarske. U naredne četiri godine rata (završio je 1238. ili 1239. godine) ugarska vojska je zaposjela samo dijelove sjeverne Bosne i sjeverozapadnog Huma. Rat je prouzrokovao mnogo štete Bosni, pa iako su Ugari proglasili pobjedu i istrebljenje bogumila, Matej Ninoslav se i dalje održao na vlasti. Koliko je rat bio iscrpljujući i za križare i za Bošnjane, najbolji je pokazatelj što je novom biskupu Johanu bilo svega dosta u tolikoj mjeri da je od pape tražio da ga razriješi nove dužnosti. Bosna je ostala potpuno jedinstvena, čemu svjedoči podatak da je od svih bosanskih velikaša jedino spomenuti usorski knez Sibislav bio uz križarsku vojsku, dok su svi ostali bili na strani bosanskog bana i njegovog naroda, koji je svim silama branio Bosnu. Ipak, treba imati na umu da ni sam Sibislav protiv Ninoslava nije ratova zbog vjerskih uvjerenja, već zbog toga što je za sebe želio bansku vlast. Na kraju ovog poglavlja treba naglasiti da pojedini historičari, poput Nade Klaić, tvrde da uopće nije došlo do križarskog rata protiv Bosne, već da je zemlja “Ninoslava i Prijezde” u Rimu predstavljena kao “pravovjerna”, isključivo vještom politikom “velikog bana” Ninoslava. Ipak, da je do križarskog rata došlo ili ne, činjenica je da je Bosna zadržala svoju samostalnost i svog vladara.
Dokaz opstanku Bosne i bana Ninoslava je trgovački ugovor iz marta 1240. godine. Ugovor je sklopljen između bosanskog bana i Dubrovnika – ugovor o trgovini i prijateljstvu. U toj povelji ban Ninoslav samosvjesno izjavljuje: “Ja Matej Ninoslav, po milosti božijoj veliki ban bosanski”. Stanje po bana se dodatno poboljšalo nakon Tatarskog upada u Ugarsku i teškog poraza ugarske vojske u Bici kod rijeke Šaj 1241. godine. U toj bici poginuo je i Koloman, kome je bila namijenjena uloga novog vladara Bosne. Obzirom da je u Ugarskoj nastalo rasulo, pa je čak i kralj Bela IV počeo da bježi na sjever zemlje, bosanska vojska je iskoristila taj događaj i krenula u kontraofanzivu te povratila izgubljeni teritorij, sjeverne Bosne i sjeverozapadnog Huma. Ban Ninoslav se poče svetiti onima koji su bili na strani pape u Bosni. Nakon toga ban Ninoslav se umiješa i u nesuglasice grada Trogira i Splita. Bosanska vojska stade na stranu Splita koji se pobunio protiv ugarskog vladara Bele IV te sukob završi uspješno po Splićane. Bilo je jasno da se ban Ninoslav sveti svima onima koji su bili, direktno ili indirektno, protiv Bosne i njegove vlasti.
Ovakav razvoj događaja ugarski kralj Bela IV, je shvatio kao veleizdaju, te 1244. godine šalje dvije armije, jednu na Split a drugu na Ninoslava. Detalji oko rata nisu poznati osim da je ugarska vojska pokorila jedan bosanski grad Glaško i da je mir potpisan 20. jula 1244. godine između bana Ninoslava i bosanskog plemstva sa jedne strane i ugarskog kralja sa druge strane. Prema pregovorima koji su trajali u gradu Glaškom od 15. do 21. jula, ban Ninoslav je samo nominalnu priznao ugarsku vlast te je zadržao svoju imovinu u Bosni i Slavoniji. Ipak, morao je priznati prava katoličke crkve na ranije date posjede koji su joj iste godine potvrđeni poveljom Bele IV.
Novom papi, Inoćentiju IV je 1246. godine javljeno od strane bivšeg bosanskog biskupa Ivana, kao i od ugarskih dominikanaca da zahtijevaju posebno pravo u borbi protiv bosanskih heretika. Kaločki nadbiskup Benedikt nudi papi pomoć u borbi protiv bosanskih heretika predlažeći novi križarski rat protiv Bosne. Oduševljen time Inoćentije IV daje Benediktu pravo da raspolaže imanjima nevjernika (bosanskih bogumila), a zatim ga imenuje i svojim legatom. Početkom 1247. godine papa pozdravlja i ideju Bele IV, koji nastoji povesti rat protiv bosanskih heretika. Kaločki nadbiskup i bosanski biskup su otišli pred papu kako bi ga uvjerili da bosanska biskupija ne pripada rimskoj crkvi, i da je treba podložiti kaločkoj crkvi. Ovakav razvoj događaja nije išao u prilog bosanskom banu. Ponovo stupa na snagu Ninoslavova vješta diplomacija, te on šalje Inoćentiju IV vjerodostojna svjedočanstva o čistoći svoje vjere, na što papa obustavlja akciju protiv Bosne. Papa je 1248. godine pisao kaločkom biskupu da je Ninoslav vjeran pripadnik katoličke crkve i plemenit čovjek. Time je Ninoslav ponovo odbio nasrtljive ugarske prelate od svoje zemlje, što mu je omogućilo da do kraja života zadrži položaj koji je stekao još 1233. godine – položaj samostalnog bosanskog vladara, “velikog bana”.
Početkom naredne, 1249. godine, ban Ninoslav sa Dubrovnikom potvrđuje ugovor o trgovini i prijateljstvu iz 1240. godine. Dubrovčani pišući ovaj tekst nisu znali da je Ninoslav već umro, pa su kasnije morali izmijeniti neka mjesta, te tako izmijeniti i povlasticu dragocjenog svjedočanstva o političkoj promjeni u Bosni. Promjene su nastale na način da je jednina zamijenjena množinom, a ime vladara je kasnije u Bosni brisano. U Bosni su također kasnije drugom rukom dodana imena četrnaestorice bosanskih velikaša. Na osnovu toga saznajemo da je mjesto “velikog bana” preuzeo jedan od Ninoslavovih sinova – veliki ban Stjepan, koji je izbrisao očevo ime i stavio svoje. Prema tome, u još nedovoljno poznatim okolnostima, nakon Ninoslava vlast preuzima njegov sin Stjepan.