Татары преследовали его по пятам вплоть до Далмации, где Бела с семьей, казной и короной нашел убежище на одном из островов Адриатики. В это время Беле IV было 35 лет. А самостоятельно править страной он начал совсем недавно — в 1235 г. умер его отец Эндре II, с которым у него были сложные, временами враждебные отношения. За время правления отца позиции королевской власти заметно ослабли. И вот теперь Бела, наконец, мог приступить к задуманным преобразованиям. В первую очередь Бела расправился с ближайшими сторонниками и придворными отца, возложив на них ответственность за беспорядок в стране. В полную силу он обрушился на магнатов, отбирая у них пожалованные им ранее земли королевского домена. Чтобы укрепить свой авторитет, новый король заставил баронов стоять в его присутствии на заседаниях королевского совета и сжег кресла, в которых обычно сидели члены совета. Бела ввел новый порядок подачи прошений 180 и жалоб: отныне они принимались только в письменной форме. Таким образом, дела в королевском суде могли рассматриваться по степени важности. Все эти мероприятия, вопреки ожиданиям короля, только раздражали подданных и усиливали напряжение в обществе. Наконец, стремясь укрепить восточную границу, в 1239 г. король принял в качестве подданных и поселил в Венгрии кочевников-половцев во главе с их князем Ке тонем, теснимых с востока монголо-татарами. Это были не первые контакты венгерского короля со степным народом. Уже в первой половине 20-х гг. половцы появились недалеко от венгерской границы и некоторые из их князей стали просить покровительства у Белы, в то время правившего Трансильванией. В 1226/27 г. при содействии доминиканцев Бела приступил к крещению половцев. В 1232 г. за Карпатами было создано миссионерское епископство. В 1233 г. он принял титул короля половцев