Закладена за Альморавідів фортеця, що панувала над долиною річки Бу-Регрег, набула особливого значення за часів Альмохадів. Халіф Абу Юсуф Якуб аль-Мансур, що правив у 1184—1199 роках, збудував портал головних кріпосних воріт (на ньому збереглися незвичні для арабського мистецтва зображення тварин). Закладену за аль-Мансура велетенську мечеть Хасана так і не було завершено і призначене для її будівництва каміння було використано для інших цілей. Поруч із фундаментом мечеті із залишками колон зберігся також недобудований мінарет Хасана висотою 44 метри. З падінням Альмохадів фортеця занепала.

З кінця XVI ст. серед руїн Касби почали оселятись біглі мориски з міста Орначос в іспанській Естремадурі. Після указів про вигнання морисків іспанського короля Філіпа III 1609 року, до Сале прибули нові вигнанці й навколо Касби виникло поселення Нове Сале (сучасний Рабат), засноване морисками, що були масово вигнані з іспанської Андалусії. Одним із головних промислів новоприбулих морисків було піратство, спрямоване проти іспанського мореплавства. Приблизно в 1624 році мешканці Касби Удая, Нового Сале та Старого Сале заснували незалежну від марокканського султана корсарську Республіку Сале, а Касба Удая стала її неформальною столицею. Незалежна республіка проіснувала до 1668 року, коли її повністю підкорив собі султан Марокко Мулай аль-Рашид із династії Алавітів (яка править Марокко і в XXI столітті)

За Алавітів у 1666—1672 та 1757—1792 роках, фортецю було знову відбудовано.