À partir de 2003, Mohammed ben Nayef, alors assistant du ministère de l'Intérieur, coordonne une campagne contre Al-Qaïda en Arabie saoudite[2]. Il forme notamment des « centres de réhabilitation » où des prisonniers djihadistes reçoivent des cours de théologie, de culture générale ou encore des prêches religieux[2]. Al-Qaïda est démantelée en Arabie saoudite et trouve refuge au Yémen où elle fonde Al-Qaïda dans la péninsule arabique (AQPA) en 2009[2]. Entre 2004 et 2015, Mohammed ben Nayef est la cible de quatre tentatives d'assassinats, il est notamment blessé dans son palais, le , par un kamikaze d'AQPA[2],[3].
Son père, ministre de l'Intérieur depuis 1975, meurt en et son oncle Ahmed ben Abdelaziz devient ministre de l'Intérieur. Ce dernier est limogé le et remplacé par Mohammed ben Nayef qui devient ainsi le plus jeune de sa génération dans la dynastie saoudienne à obtenir un poste aussi élevé, en faisant dès lors un prétendant au trône[4].
Prince héritier et vice-Premier ministre
En , après la mort du roi Abdallah et par un décret royal du nouveau roi Salmane[5], il est nommé prince héritier en second, derrière le prince Moukrine. Le [6], le prince Moukrine est écarté de la succession et Mohammed ben Nayef lui succède donc au double poste de prince héritier et vice-Premier ministre[6]. Il devient par la même occasion président du Conseil des affaires politiques et de sécurité nouvellement créé.
Le , il est décoré de la Légion d'honneur par François Hollande « pour tous ses efforts dans la région et dans le monde dans la lutte contre le terrorisme et l’extrémisme »[7]. Qualifié de pratique protocolaire courante par l'Élysée, cette initiative est critiquée par des hommes politiques de droite comme de gauche et a entraîné le refus de la Légion d'honneur par Sophie Marceau[8].
Éviction de l'ordre de succession et ostracisation progressive
Le , il est évincé de toutes ses fonctions par le roi Salmane qui nomme par décret son fils Mohammed nouveau prince héritier[10],[11],[12].
En , Mohammed ben Nayef est accusé de complot visant à renverser le roi Salmane et le prince héritier Mohammed ben Salmane, il est arrêté, tout comme son demi-frère Nawaf Ben Nayef et Ahmed ben Abdelaziz Al Saoud, frère du roi Salmane. Cette arrestation est perçue comme un moyen, pour Mohammed ben Salmane, d'empêcher qu'un autre prince saoudien puisse devenir le prochain roi[13],[14].