À peine son autorité fut-elle affermie, qu’au surplus il remit le gouvernement entre les mains de son frère Omar et alla se faire légitimer en grande pompe à la Mecque et au Caire (1497).
« Il fit le pélerinage à la Maison de Dieu accompagné de mille fantassins et de cinq cents cavaliers, emportant 300.000 mitkals d’or du trésor de Sunni Ali. Il en répandit 100.000 aux Lieux Saints, tant à Médine où est le tombeau du Prophète qu’à la Mecque où s’élève la Mosquée sacrée. Dans cette dernière ville, il acheta des Jardins et y établit une fondation pieuse pour les gens du Soudan. Cette fondation est bien connue à la Mecque et lui coûta cent mille mitkals.
« Au retour, il vint en Égypte rendre hommage au khalife abbasside Mottewekel, et lui demander d’être son suppléant au Songhoï et dans tout le Soudan. Le prince abbasside ayant consenti, ordonna au roi songhoï d’abdiquer et de remettre le pouvoir entre ses mains pendant trois Jours. Ainsi fut fait. Le quatrième jour, Mottewekel proclama solennellement Askia Mohammed représentant du khalife au Soudan, lui plaça sur la tête un turban blanc et un fez vert qui lui appartenaient, et lui remit un sabre. »
Ce pélerinage eut une autre conséquence plus importante encore pour son règne et surtout pour ses sujets. Au Caire il s’entretint assidûment avec les théologiens et les savants réputés, se montrant curieux de toutes choses et empressé à recueillir des conseils sur les meilleures manières de vivre et de gouverner. Il se lia en particulier avec Essoyouti dont le nom est encore aujourd’hui célèbre dans les lettres arabes. De retour au Songhoï, Askia entra en correspondance avec lui, et chaque fois qu’il songeait à une réforme ou à une mesure importante, il ne manquait pas de la soumettre au savant personnage. Incontestablement, c’est au Caire qu’il acquit les notions de gouvernement qui, appliquées par son génie organisateur, vont lui permettre d’édifier une œuvre
