Для столицы своей созданной империи Идрис ибн Абдуллах решил построить новый город на правом берегу реки Фес в 789 году. Многие из первых его жителей были беженцами, бежавшими от восстания в Кордове (современная Испания)[1]. Но в 809 году его сын Идрис II решил основать собственную столицу на противоположном берегу реки Фес. Множество беженцев осели в Фесе после восстания в Кайруане (современный Тунис)[1].

Несмотря на то, что они были разделены только относительно небольшой рекой, города развивались отдельно и стали двумя отдельными городами, пока они не были объединены в XI веке Альморавидами.

Одним из примеров того, какую роль беженцы играли в развитии Феса в первые годы его существования, является тот факт, что университет Аль-Карауин, который был построен тунисским беженцем в 859 году, ныне считается старейшим постоянно действующим университетом в мире[2].

В период правления Альморавидов Фес потерял свой столичный статус после основания Марракеша и перенесения столицы туда.

Альморавиды разрушили большую часть Феса эль-Бали, но сумели создать современный Фес эль-Бали, когда они объединили города по обе стороны реки Фес, разрушив то, что их разделяло, и построив мосты через реку.

Во время правления Альмохадов Фес был процветающим торговым городом, хотя и не был столицей. Его население тогда составляло около 200 000 человек, что делало Фес одним из крупнейших городов мира в то время[3].

После победы над Альморавидами в Марокко Мариниды перенесли столицу из Марракеша обратно в Фес[4]. Это ознаменовало начало крупнейшего периода расцвета в истории Феса эль-Бали[4]. Когда Мариниды перенесли столицу в Фес в 1276 году, они начали строить новый город за пределами старых городских стен. Сначала он назывался белым городом[4], но через некоторое был переименован в Фес Дждид, или Новый Фес. Именно тогда Фес эль-Бали, или Старый Фес, получил своё нынешнее название.

Большинство главных архитектурных памятников в Фесе эль-Бали были построены при правлении Маринидов. Среди них Андалузская мечеть[en] и Мечеть Баб-Гисса. В XIV веке в состав города была включена мелла (еврейский квартал).