Al Mukalla está situada cerca de "Qana'", el antiguo puesto de comercio de Hadrami, entre India y África, con el incienso como principal producción de áreas en su hinterland.[1]​

Al Mukalla fue fundada en 1035 como poblamiento de pescadores. Esta área estuvo incluida en el estado de Omán hasta mediados del siglo XI, y más tarde fue incluida en los estados de Yemen.

Fue la capital del estado de Qu'aiti en Hadhramaut hasta 1967 que pasó a ser una parte de Yemen del Sur. El estado de Qu'aiti formó parte del Protectorado de Adén Oriental hasta aquella fusión.

En 1934, el explorador y viajero británico Freya Stark empezó su viaje a Hadhramaut desde Al Mukalla, y su estancia en aquella ciudad consta en su libro, Las Puertas del sur de Arabia.[2]​

El 2 de abril de 2015, Al-Qaeda en la Península arábiga (AQAP) tomó la prisión central, liberando a centenares de los prisioneros que incluían dos antiguos comandantes de la organización. Atacaron el banco central y robaron 17 mil millones de reales yemeníes y 1 millón de dólares antes de tomar control del palacio presidencial en la ciudad. Actualmente, la ciudad entera está bajo su control y planean establecer un emirato islámico en la región de Hadramaut.[3]​