Века римского (а до того во многих местах карфагенского) владычества не прошли даром, и в берберском обществе произошли значительные изменения. Верхушка многих племен романизировалась. Но все же можно говорить о возрождении берберской цивилизации. Характерно, что в одном из таких государств выпускаемые там монеты давали имя правителя в нумидийской форме и нумидийскими буквами: MNASMA. Роль берберского элемента еще более увеличилась в связи с усиленным проникновением берберов извне. Южная граница Вандальского королевства никогда не была четко обозначена и всегда оставалась проницаемой. Отдельные небольшие гарнизоны не могли сдержать берберов, стремившихся, как и те же вандалы, занять более благодатные земли бывших римских провинций. Племена из пустыни или из гор занимали более плодородные территории. Местное население порой пыталось организовать сопротивление. Известно об одном епископе, который погиб в борьбе с маврами. Города, как упоминалось выше, окружали себя новыми стенами, не обращая внимания на королевский запрет. Но не получая действенной помощи от власти, сопротивляющиеся терпели поражения. Все больше территории, особенно в Мавретании, ускользало из-под реального контроля королевской власти. Там образовывались собственные государства. И это были не эфемерные племенные образования, а относительно обширные и хорошо организованные царства. Под власть местных царьков попадали и города. Точные пределы этих государств неизвестны, но ясно, что все большая часть сначала Мавретании, а затем Триполитании переходила под их власть. Берберские правители порой принимали пышные титулы царей. Так, Масуна именовал себя царем племен мавров и римлян (rex gentium Maurorum et Romanorum), а другой вождь — Мастиес — даже провозгласил себя императором, заявив, что он был вождем, а затем стал императором. Мастиес также объявлял себя правителем и мавров, и римлян. Полагают, что он осмелился принять титул императора после исчезновения императорской власти на Западе, предъявляя тем самым претензии на наследование римских императоров. Его «империя» возникла, вероятно, в результате восстания горцев в Нумидии и Мавретании. Тем не менее романское население и в этой «империи», и в государстве Масуны составляло значительную часть и было, по крайней мере, теоретически равноправным с берберами. В государстве Масуны сохранились старые римские порядки. Префекты управляли отдельными территориями и укреплениями (castra), хозяйственными вопросами занимались прокураторы. Мастиес подчеркивал, что он никогда не был клятвопреступником ни по отношению к маврам, ни по отношению к римлянам. Может быть, такое подчеркивание роли римлян в своих государствах было и для Масуны, и для Мастиеса вызовом по отношению к вандальским королям. Эти и подобные им государства. расположенные сравнительно далеко от основного ядра Вандальского королевства, явно были независимыми от вандальских королей и, скорее, предъявляли претензии на преемственность, идущую от римской власти. Они образовались относительно поздно, когда власть вандалов начала ослабевать, и поэтому сразу же вступили в конфронтацию с ними. Те же государства, которые находились ближе к этому ядру или возникли в период вандальского завоевания либо вскоре после него, признавали свою зависимость от королей, что не мешало в ряде случаев им использовать ситуацию для выступления против вандалов.
Фактическим создателем Вандальского государства и его могущества был Гейзерих. Сын короля Годигисела и рабыни, он стал королем еще в Испании после смерти своего сводного брата Гундериха в 428 г. Через год он возглавил переселение вандалов и аланов в Африку. Незадолго до своей смерти он заключил договор с Одоакром. по которому уступал тому Сицилию, кроме Лилибея. Правда, официально Одоакр обязался платить Гейзериху ежегодный налог, что означало официальное признание того господином острова. Но это была лишь формальность, которая должна была «подсластить пилюлю» и сохранить авторитет грозного короля в глазах соплеменников. Еще до этого Гейзерих заключил союз с фактически правившим Италией Орестом. По-видимому, и заключение «вечного мира» с Зеноном, и союз с Орестом, и договор с Одоакром были вызваны стремлением Гейзериха урегулировать ситуацию в Средиземноморье. Путем некоторых уступок он надеялся (и небезуспешно) стабилизировать положение собственного государства. Вандальское королевство должно было стать не столько угрозой для других государств, каким оно было на протяжении нескольких десятилетий, сколько равноправным элементом общей политической системы.