Après le départ des Romains, on ignore le sort du fortin – si toutefois il a existé. La région est devenue une région de parcours pour des populations nomades ou semi-nomades, à la recherche constante de pâturages et d'eau pour leurs troupeaux d'ovins et de camélidés. En dépit de l'islamisation, la steppe est restée largement berbère. Cependant, à partir du XIe siècle, des bouleversements surviennent qui vont changer la physionomie du pays. C'est à cette période, en effet, que déferlent, sur les régions steppiques et sahariennes, les tribus arabes des Banu Hilal et Sulaym. A l'origine de cette invasion, il y a la vengeance des Fatimides – dynastie chiite installée au Maghreb – qui voulaient se venger des princes berbères qui refusaient de leur faire allégeance. Les tribus arabes, chassées du Hedjaz par la famine, étaient jusque-là contenues en Egypte : les Fatimides les lâchent sur le Maghreb. Ils écument l'Egypte et la Libye et arrivent aux portes de l'Ifriqiya, c'est-à-dire la Tunisie et l'est de l'Algérie, qui faisaient partie du royaume ziride. Les nomades pillent les villes et les villages du Nord, avant de s'éparpiller dans les zones désertiques où elles s'acclimatent. Elles chassent les populations autochtones et arabisent de vastes zones, restées jusque-là, berbérophones. C'est le cas de Boussaâda.
