Il est formellement déconseillé de se déplacer seul, sans escorte ni chauffeur, sur les routes. Il est théoriquement possible de louer une voiture sans chauffeur, mais de toute façon, la location revient presque aussi chère qu'une voiture avec chauffeur. Ensuite, à moins de connaître vraiment bien le pays et la langue arabe, vous auriez beaucoup de mal à trouver votre chemin (très rares indications routières).

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), il vous fera faire des découvertes que vous n'auriez pas faites seul.
Le forfait quotidien demandé inclut l'essence, le chauffeur (sa nourriture et son logement). Vérifier l'état de la voiture avant de partir. Le repas et l'hébergement du chauffeur ne sont pas inclus, mais vous pouvez toujours lui offrir un petit quelque chose. À titre indicatif, la location d'un 4x4, comprenant un chauffeur et l'essence, revient entre 50 et 100 US$ par jour environ.
Entre les grandes villes, les routes sont asphaltées, tandis que les routes secondaires sont souvent des pistes non balisées (4x4 nécessaire).
Pour traverser le rub (désert) Al-Khali en voiture, vous ne pourrez pas vous passer des services des Bédouins. Compter, en plus du chauffeur, 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. C'est chez eux et c'est comme ça... Idem pour Shaharan : ce sont les Bédouins qui décident.
De manière générale, il est déconseillé de prendre la voiture de nuit.

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. Mieux vaut réserver 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.

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 ne demandent pas d'argent aux étrangers.

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

C'est sans doute l'idéal pour un routard, mais la marche exige beaucoup de temps. Au Yémen, ele 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.
Le trek est par ailleurs un but en soi, que programment de nombreuses grandes agences de voyages.