Vijeće je napade opisalo kao "gnusan čin" i obećalo da će se boriti protiv svih oblika terorizma.
Ogranak Al-Kaide u Jemenu je priznao da je jedan on njihovih članova izveo napad na trgu u blizini predsjedničke palate.
Predsjednik Jemena Abd Rabbo Hadi Mansour je obećao čvršće i odlučnije akcije protiv militanata.
"Rat protiv terorizma će se nastaviti dok ga ne iskorijenimo i ne uništimo u potpunosti, bez obzira na žrtve koje moramo podnijeti", kazao je Hadi.
Predsjednik Hadi, koji je na vlast došao u februaru, je obećao da će izbaciti militante iz južnih i istočnih provincija, koje i imaju najveće probleme sa teroristima. Jedna od južnih provincija, Abyan je od prošle godine pod kontrolom Ansar al-Sharie, ogranka Al-Kaide Arabijskog poluotoka (AQAP).
Eksplozija se desila u ponedjeljak za vrijeme priprema za vojnu paradu. U izvještajima se navodi da su povrijeđene 222 osobe, prenosi BBC.
Svjedoci su izjavili da su bombaši samoubice bili u vojnim uniformama.
"Većina povreda je u predjelu glave. Mnogo je paralizovanih. Očekujemo da će mrtvih biti još više. Većina povrijeđenih su tinejdžeri", kazao je Mohsen al-Dhahari, lokalni ljekar.
AQAP je preuzeo odgovornost za napad za koji tvrdi da mu je cilj bio ministar odbrane i druge vođe koji pomažu Sjedinjenim Američkim Državama da vode rat protiv naroda u Abyanu.
"Čak i ako ministar odbrane Mohammed Nasser Ahmed i njegovi saveznici prežive ovaj napad, mi nećemo posustati. Mi smo u ratu kojim branimo svoju krv u Abyanu", stoji u izjavi na forumima džihadista.