Mukalla was founded in 1035 as a fishing settlement. This area was part of Oman until the middle of the 11th century, and later this area became part of Yemen. After witnessing a struggle for control by the Kathiri and Qu'aiti Sultanates in the 19th and 20th centuries, it became the capital of the Qu'aiti State of Hadhramaut, and then in 1967, it became a part of South Yemen. The Qu'aiti Sultanate was part of the Eastern Aden Protectorate until that merger, and a British Resident Advisor was stationed at Mukalla. The other major cities of the Sultanate were Ash-Shihr and Shibam.