Il est théoriquement possible de louer une voiture sans chauffeur et Hertz possède même un bureau à Sanaa (tél. : (01) 440-309) et un à Aden (tél. : (02) 245-625). D'autres petites agences locales louent également des 4x4.
Mais franchement, on ne vous recommande pas cette solution pour tout un tas de raisons. D'abord, elle revient presque aussi chère qu'une voiture avec chauffeur. Ensuite, à moins que vous ne connaissiez vraiment bien le pays et la langue arabe, vous aurez beaucoup de mal à trouver votre chemin (très rares indications routières), et risqueriez de perdre un temps précieux en vous embarquant sur de mauvais chemins.

Le bus

S'il est tout à fait possible d'utiliser les transports en commun, il faut savoir qu'ils n'empruntent que les axes routiers desservant des villes importantes : Sanaa, Mareb, Hodeïda, Hajja, Aden, Mukalla et quelques autres (se renseigner à l'office du tourisme de Sanaa, près de la poste principale). Cependant, même si le réseau routier s'améliore d'année en année, de nombreux sites et villages ne sont accessibles qu'en 4x4, et c'est tant mieux !
Ils sont réguliers et les places sont numérotées. Leurs tarifs sont dérisoires. Réservez la veille. Les billets s'achètent dans les gares routières ; il est impossible d'en acheter dans les bus.
Outre les bus locaux parfois à mille lieues des exigences de confort occidental, une compagnie, Yemit Co, propose sur les mêmes trajets des cars Mercedes modernes et climatisés. Un peu plus cher, mais équipés de sièges couchettes. Pas négligeable, vu la longueur des voyages.

Les taxis collectifs

Ils partent des gares spéciales « taxis ». Le moins que l'on puisse dire, c'est qu'ils sont le meilleur moyen de rencontrer les Yéménites. Ces vieux véhicules partent quand ils se considèrent pleins, avec une notion particulière du « plein ».
C'est le moyen de transport le plus économique après le stop et la marche, si l'on ne souffre pas de claustrophobie et qu'on ne craint pas la conduite « sportive » des chauffeurs toujours pressés (comme les passagers...). D'ailleurs, certains chauffeurs rechignent à embarquer des touristes qui, soumis aux contrôles de police, risquent de retarder.
Selon le parcours emprunté, les taxis ont des bandes de couleur différente.
On négocie le prix avant le départ. Les taxis collectifs ont des tarifs fixes, de même que les autocars.

La voiture avec chauffeur

C'est la solution idéale pour plusieurs raisons : formalités simplifiées (l'agence s'occupe des autorisations), gain de temps, sécurité, liberté d'action (départs, arrivées, arrêts, détours...). Si le chauffeur est coopératif (c'est souvent le cas) et futé, il vous fera faire des découvertes que vous ne feriez pas seul. Il est bien sûr plus intéressant de partager la location à plusieurs.
Le forfait quotidien demandé inclut l'essence, le chauffeur (sa nourriture et son logement). Le repas et l'hébergement du chauffeur ne sont pas inclus, mais vous pouvez toujours lui offrir du qât, sans vouloir pousser à la conso, il appréciera toujours. À titre indicatif, la location d'un 4x4, comprenant un chauffeur et l'essence, revient à peu près entre 50 et 100 US$ par jour.
Pour traverser le rub (désert) Al-Khali en voiture, vous ne pourrez pas vous passer des services des Bédouins (compter environ 150 à 300 US$ par traversée, quel que soit le nombre de personnes et - en principe - de véhicules, ce que certaines agences se gardent bien de dire, taxant chaque véhicule du convoi), en plus du chauffeur. C'est comme ça et c'est chez eux... Idem pour Shaharan : ce sont les Bédouins qui décident.

L'auto-stop

Possible sur les grands axes, très aléatoire sur les pistes et routes secondaires. Les camions vous prendront sans difficulté, mais les chauffeurs, n'étant pas philanthropes, vous demanderont normalement une rémunération du même montant que le taxi collectif assurant la même liaison. Les Yéménites paient selon ce système. Toutefois, on peut marchander. Renseignez-vous sur le prix avant pour pouvoir discuter. Il arrive aussi que des conducteurs aient la délicatesse de ne pas demander d'argent aux étrangers. Internet : www.bazaratravel.com.

L'avion

Si vous êtes seul et pressé, vous n'y échapperez pas. Pratique, mais assez cher pour les longs trajets vers l'Hadramaout (il ne remplace pas la traversée du désert en 4x4 ! mais fait gagner deux jours, enfin... si l'avion décolle).
Yemenia assure la majorité des liaisons intérieures et propose parfois des réductions, si vous avez voyagé chez eux pour le vol international. Renseignez-vous avant d'acheter votre billet.

La marche à pied

Sans doute l'idéal pour un routard, pourtant ce moyen de visiter exige beaucoup de temps car il ne faut pas oublier que le Yémen est presque aussi étendu que la France. Il nécessite une bonne condition physique en raison des changements d'altitude et de climat, et beaucoup de patience car l'auto-stop (voir plus haut) n'est pas une pratique courante.
La marche sportive, le trek comme on dit maintenant, est par ailleurs un but en soi, que programment de nombreuses grandes agences de voyages.