– Al Qaida inntok hovedkvarteret til 2. militærregion i ettermiddag uten motstand, sier en offiser i Jemens militære til nyhetsbyrået AFP.
Offiseren sier at de jemenittiske styrkene på basen trakk seg tilbake til en flybase utenfor byen, et av de få områdene i Mukalla som ikke er under Al Qaidas kontroll.
Al Qaida-styrkene skal ha sikret seg våpen og utstyr fra basen, og også ranet en bank.
Mukalla er en havneby knyttet til Adenbukta, i provinsen Hadramawt sørøst i landet.
Se kart nederst i saken.
Øyenvitner rapporterer om at Al Qaida-styrker har paradert gjennom byen med svarte flagg, mens mange innbyggere rømmer fra byen.
I går stormet Al Qaida et fengsel i Mukalla og satte fri 300 fanger, blant dem en leder av terrororganisasjonen.
- Les også:
Farligste grenen av Al Qaida
Al Qaida i Jemen kaller seg Al Qaida på den arabiske halvøy (AQAP) og er regnet som den farligste grenen av Al Qaida.
Terrororganisasjonen har stått bak flere angrep de siste årene, både mot vestlige mål og mot mål i Saudi-Arabia.
AQAP har blant annet tatt på seg ansvaret for forsøket 1. juledag 2009 på å sprenge et fly i luften over Detroit ved hjelp av en bombe gjemt i underbuksen.
De to brødrene som angrep det franske satirebladet Charlie Hebdo i januar, Saïd og Chérif Kouachi sa begge til et øyenvitne at de var medlemmer i AQAP.
USA har i flere år rettet omfattende droneangrep mot AQAP; noe som begrenset deres mobilitet og synlighet.
Land i oppløsning
FNs nødhjelpssjef Valerie Amos sa torsdag at 519 mennesker var drept og nærmere 1.700 såret i løpet av de to siste ukenes kamper.
En koalisjon ledet av Saudi-Arabia startet angrepet mot Jemen med kodenavnet «Operation Decisive Storm» 26. mars. Etter angrepet har Jemen i stadig større grad blitt delt opp i forskjellige maktsentre.
Houthi-militsen har i hovedsak kontroll over hovedstaden Sanaa og landets nest største by Taez, mens det pågår kamper mot det forrige regimet i den strategisk viktige byen Aden.
Nå ser det ut til at Al Qaida har etablert over Mukalla og store områder sørøst i landet.