En explosion har även hörts i närheten av presidentpalatset.
Landets informationsminister anklagar Huthirebellerna för attacken mot flygplatsen. Enligt en säkerhetskälla träffade tre granater flygplatsen.
Över 50 personer skadades, enligt sjukhuskällor.
Nyhetsbyrån Reuters källor anger minst 20 dödsoffer och minst 17 skadade.
-Minst två explosioner hördes när regeringsföreträdarna lämnade flygplanet, säger en korrespondent för nyhetsbyrån AFP.
Flyende människor
Rök steg från flygplatsbyggnaden efter händelsen, visar bilder från den saudiska tv-kanalen al-Hadath. Bilder från platsen visar också människor som springer från flygplatsbyggnaden, och förödelse i vänthallarna efter explosionerna.
Regeringsföreträdarna, bland dem landets premiärminister Main Abd al-Malik Said, fördes oskadda till stadens presidentpalats efter dådet, meddelar vittnen och saudiska medier.
En explosion har hörts även vid presidentpalatset, men det finns inga uppgifter om eventuella skador. Uppgiften om den misstänkta explosionen har inte heller bekräftats av myndigheterna.
Många hade samlats
Många hade samlats på flygplatsen för att möta den nytillträdda regeringen, som anlände bara dagar efter att ha svurits in av den jemenitiske presidenten Abd-Rabbu Mansour Hadi i Saudiarabien.
Tiotusentals människor, främst civila, har dödats och miljoner har tvingats lämna sina hem under det fem år långa kriget i Jemen, som FN kallat världens värsta humanitära katastrof. På ena sidan i konflikten står de Iranstödda Huthirebellerna, på den andra den internationellt erkända regeringen uppbackad av en saudiskledd militärallians.