В 818 г. халиф Мамун был вынужден направить в Южную Аравию войска для подавления усиливавшегося там сопротивления верховной власти. Войсками командовал Мухаммед бен Абдаллах бен Зияд. Расправившись с восставшими в йеменской красноморской области Тихама, Зияд захватил Аден и Хадрамаут. В 819 г. он основал город Забид, который объявил столицей независимого от аббасидского халифата княжества Зиядидов.
Упадок могущества халифата явился причиной появления на юго-западе Аравии и других независимых мелких и мельчайших княжеств и шейхств, враждовавших между собой. Относительно крупным среди них было государство Зурейядов в Адене (1070–1175). Стремясь не допустить усиления власти Зурейядов, правительница Йемена Сейида бинт Ахмед ас-Сулейхи (1083–1138), более известная под именем Арва, хитростью заманила в Забид, где находилась ее резиденция, главу семейства Зурейядов — Зурейя бен аль-Аббаса и приказала убить его. Родственники убитого немедленно заявили от отказе признавать власть Сулейхидов и платить им дань. Арва послала в Аден войска, но они не смогли рагромить южнойеменцев. Однако впоследствии борьба за власть внутри династии Зурейядов помешала Адену возвыситься в качестве политического центра. Итогом этой борьбы явилось восстановление в 1138 г. господства Сулейхидов.
В 1174 г. в Йемен прибыло трехтысячное войско султана Египта и Сирии Салах ад-Дина (Саладина), основателя династии Айюбидов, под командованием его брата Туран-шаха. Оккупировав Тихаму, войска Айюбидов захватили в 1175 г. Аден, а затем заняли всю страну, подавив сопротивление ополчений карликовых государств.
Наместником Туран-шаха в южных районах Йемена был назначен сириец аз-Занджибейли, ставший после смерти Туран-шаха фактически самостоятельным правителем.
Аз-Занджибейли вошел в историю Адена как один из наиболее просвещенных правителей. Он всячески содействовал возрождению торговой активности аденского порта и экономическому развитию районов, окружавших Аден. В качестве советников аз-Занджибейли пригласил в Аден опытных законоведов из Сирии и других частей халифата. Для усиления обороны Адена от нападений с моря он приказал укрепить имевшиеся крепостные сооружения и построить новые. В 1183 г. аз-Занджибейли возвратился в Сирию.
Айюбиды правили в Адене до 1229 г., когда их наместник Мансур Нураддин поднял восстание против султана и основал династию Расулидов (1229–1453). Эта династия признавала формальный сюзеренитет багдадского аббасидского халифа, но на деле правила Йеменом по своему усмотрению.
При Расулидах Аден посетили венецианец Марко Поло (1254–1323) и марокканец Ибн Баттута (1304–1377). Великие путешественники оставили потомкам описания Адена (равно как и сотен других городов), а не только упоминание его названия в связи с какими-то историческими событиями и восстановили утраченную более чем на тысячелетие традицию «Перипла Эритрейского моря».
Марко Поло путешествовал около 17 лет, Ибн Баттута — около 28. Поэтому вызывает восхищение их феноменальная память, сохранившая картинки жизни Адена — незначительного пункта на их многолетних маршрутах. Приведем их высказывания об Адене.
Вот что писал (вернее, диктовал) о нем Марко Поло: «Живут тут сарацины, молятся Мухаммеду, а христиан ненавидят. Много тут городов и замков, и есть пристанище, куда приходят суда с товарами из Индии; много купцов приходит сюда… Этим путем получают сарацины в Александрии и перец, и пряности, и дорогие товары; другого пути в Александрию нет. Везут из этой пристани в Индию много красивых да дорогих арабских скакунов; и большая купцам прибыль от этого товара…
Султану аденскому большой доход и много богатства от пошлины с судов и купцов, бывающих здесь».
Судя по описанию Марко Поло, Аден уже был в то время крупным торговым портом. Не зря средневековые купцы называли Аден «первым рынком Аравии». Марко Поло подтверждает это, когда пишет, что в порту Шихр (расположенном близ нынешней Мукаллы) чиновники аденского султана взимали крупные пошлины с торговцев благовониями.
Примерно в 1330 г. в Аден из Северного Йемена прибыл Ибн Баттута, которого иногда называют соперником Марко Поло. В своей книге «Подарок созерцающим о диковинках городов и чудесах путешествий» Ибн Баттута рассказывает об Адене следующее: «Он окружен горами, поэтому к нему можно приблизиться лишь с одной стороны. В нем нет ни посевов, ни деревьев, ни воды, но есть резервуары для сбора дождевой воды. Арабы часто прекращают доставку жителям питьевой воды, пока те не откупятся деньгами и одеждой. Это город с чрезвычайно жарким климатом. Он служит портом для индийцев, и сюда прибывают крупные суда из Камбея, Таны, Каулема, Каликута и многих других малабарских портов.