Poslije bana Kulina (1204) neko vrijeme je Bosnom vladao ban Stjepan o kome nemamo puno podataka, osim da je imao sina Sibislava, kneza Usore. Novi ban se prvi put javlja u izvorima 1233. godine, kao ugarski vazal – ban Matej Ninoslav. Da bi izbjegao pritisak papske kurije prihvatio je kršćanstvo.

Ipak, u Bosni se i dalje širilo bogumilsko učenje, pa čak i izvan njezinih granica. Postavljeni 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. S tim u vezi nastojala je prouzrokovati križarski rat protiv nje kako bi se domogla njezine teritorije. Kada je darovnicom, ugarskog kralja Andrije, čitava Bosna data na upravu hercegu Kolomanu i potvrđena od pape 1235. godine, Mateju Ninoslavu je bilo jasno da više nisu u pitanju samo crkvene prilike već i da se zazire u državnu samostalnost bosanske države.

O prvom križarskom ratu protiv Bosne, koji je trajao od 1235. do 1238. godine veoma malo znamo, ali nam je poznato da je križarsku vojsku predvodio postavljeni herceg Hrvatske Koloman. Osnovni cilj rata je bilo podčinjavanje Bosne Ugarskoj, tako da je rat dobio odlike osvajačkog rata. 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 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, čemu svjedoči ugovor o trgovini između Bosne i Dubrovnika, potpisan u martu 1240. godine.