A Ryad, il n'a en revanche pas obtenu de percée dans la crise qui oppose quatre pays arabes (Arabie saoudite, Bahreïn, Emirats arabes unis et Egypte) au Qatar.
Avant de se rendre à Doha dans la soirée, le chef de la diplomatie américaine a assisté à Ryad à la première réunion de la Commission de coordination saoudo-irakienne, lancée solennellement par le roi Salmane d'Arabie saoudite et le Premier ministre irakien Haider al-Abadi.
Un Irak "indépendant et fort" va "permettre d'une certaine manière de contrecarrer les influences négatives de l'Iran" dans ce pays, a-t-il dit lors d'une conférence de presse.
"Les milices iraniennes qui sont en Irak, maintenant que le combat contre l'Etat islamique touche à sa fin", "doivent rentrer chez elles, tous les combattants étrangers doivent rentrer chez eux", a-t-il insisté.
Il faisait référence au Hachd al-Chaabi, des unités paramilitaires qui regroupent plus de 60.000 hommes, pour beaucoup issus de milices chiites soutenues par l'Iran, formées en 2014 pour suppléer les forces gouvernementales irakiennes face aux jihadistes du groupe Etat islamique (EI). "Soit ils partent, soit ils intègrent les forces de sécurité irakiennes", une grande partie de ces miliciens étant irakiens, a précisé un haut responsable américain.
Rex Tillerson a aussi appelé l'Irak et l'Arabie saoudite "à continuer à élargir cette relation vitale pour la stabilité de la région" et "pour notre sécurité collective".
"Malheureusement par le passé, les Irakiens ont eu des gouvernements (...) pas très amicaux à l'égard de l'Arabie saoudite", a dit pour sa part le ministre saoudien des Affaires étrangères Adel al-Jubeir, saluant la nouvelle dynamique.
Face à son ennemi, Ryad a entrepris de se rapprocher de Bagdad, après avoir longtemps eu des relations difficiles avec les gouvernements irakiens à dominante chiite et proches de Téhéran qui se sont succédé depuis 2003.
'Semer le chaos'
La visite de Rex Tillerson intervient moins de dix jours après la présentation par Donald Trump de sa stratégie face au régime iranien, une de ses bêtes noires, accusé de "semer la mort, la destruction et le chaos à travers le monde".
Tout en remettant partiellement en cause l'accord sur le nucléaire iranien pourtant cher à ses alliés européens, le président américain a expliqué vouloir combattre les activités "néfastes" de l'Iran notamment auprès du régime de Bachar al-Assad en Syrie, où Washington prédit désormais une ère de transition avec la "fin" annoncée du "califat de l'Etat islamique".
Le Yémen, où Téhéran soutient les rebelles Houthis contre les forces loyales au président Abd Rabbo Mansour Hadi épaulées par une coalition arabe menée par Ryad, a également été au coeur des entretiens de Rex Tillerson avec les dirigeants saoudiens.
La proximité avec l'Iran, c'est par ailleurs ce que l'Arabie saoudite, Bahreïn, les Emirats arabes unis et l'Egypte reprochent au Qatar.
Le 5 juin, deux semaines après une visite de Donald Trump à Ryad, ces quatre pays arabes ont rompu leurs relations diplomatiques avec Doha, également accusé de soutenir le "terrorisme".
Le Qatar rejette ces accusations et dénonce une tentative de "mise sous tutelle" de sa politique étrangère par ce "quartet".
Depuis, cette crise d'une gravité sans précédent pour le Golfe est dans une impasse, malgré l'optimisme de Donald Trump, qui prédisait il y a un mois une issue positive rapide.
"Nous encourageons le dialogue", s'est borné à dire Rex Tillerson à Ryad, soulignant que les Etats-Unis conservaient "des liens très forts avec tous les pays impliqués dans cette crise, y compris le Qatar".
Le secrétaire d'Etat, qui s'était déjà rendu dans la région en juillet sans succès, avait estimé avant cette nouvelle mission qu'il revenait aux dirigeants du quartet de pays arabes opposés au Qatar "de dire quand ils veulent s'engager dans le dialogue", tout en déplorant "une véritable absence de volonté de la part de certaines parties".
La tournée de Rex Tillerson le conduira ensuite pour la première fois au Pakistan et en Inde, où il évoquera notamment le conflit en Afghanistan, ainsi qu'à Genève.
Avec AFP