La présence au Yémen de Saïd Kouachi a été signalée à différents moments entre 2009 et 2013, d'abord comme étudiant à l'Université al-Imane de Sanaa, animée par des fondamentalistes, puis dans des camps d'entraînement dans le sud et le sud-est du pays, selon des sources de sécurité yéménites.
Le premier indice d'une possible implication d'Aqpa est venu de la bouche d'un des frères Kouachi lors de l'attaque qui a décimé mercredi la rédaction de Charlie Hebdo. "Dites aux médias que c'est Al-Qaïda au Yémen", a crié un assaillant, selon des témoins cités par des médias français.
"Le voyage au Yémen offre un terrain propice à l'entraînement" pour des apprentis jihadistes, relève Laurent Bonnefoy, professeur à l'Université de Sciences Po à Paris et spécialiste du Yémen.
Le séjour de Saïd Kouachi au Yémen, selon le récit d'un de ses camarades, aurait commencé en 2009. Il fréquente l'Université al-Imane, dirigée par le prédicateur fondamentaliste Abdel Majid al-Zindani, qui figure sur une liste noire américaine.
Cet établissement et d'autres instituts privés de Sanaa servaient de couverture à des réseaux extrémistes sunnites pour attirer des apprentis jihadistes des quatre coins du monde.
C'est l'un de ces instituts de langues qui a permis au jeune Nigerian, Umar Farouk Abdulmattallab, de séjourner au Yémen et d'y rejoindre Al-Qaïda avant de tenter à Noël 2009 de faire sauter un avion de ligne américain.
"Le gouvernement de Sanaa a laissé de nombreux étrangers venir étudier au Yémen, notamment dans les écoles coraniques, mais ils ne s'inscrivent pas tous dans une logique de violence", rappelle M. Bonnefoy.
"Un certain nombre de militants qui, au départ, ont une posture non violente vont évoluer vers la violence", ajoute-t-il toutefois.
Selon un responsable américain, Saïd Kouachi avait voyagé au Yémen en 2011 où il avait été formé au maniement des armes par un membre d'Al-Qaïda avant de rentrer en France.
Les autorités américaines ont souligné que les deux auteurs présumés de l'attentat étaient "depuis des années" sur la liste noire américaine du terrorisme.
Selon M. Bonnefoy, la radicalisation de Saïd Kouachi serait antérieure à son arrivée au Yémen, pays en proie à une instabilité chronique et où les ambassades occidentales sont au centre de toutes les menaces.
"Le passage au Yémen n'est certainement pas l'élément déclencheur", dit l'expert français en s'étonnant que cet homme, "qui était déjà sur des listes noires du terrorisme, n'ait pas été intercepté" aux frontières. "Il y a certainement eu des dysfonctionnements des services français et yéménites".
Pour Saeed al-Jamhi, chercheur yéménite spécialisé dans les groupes extrémistes, Aqpa a réussi une "politique de recrutement d'éléments étrangers" attirés dans le pays sous prétexte d'y effectuer des études religieuses ou d'y apprendre l'arabe.
Cela ne veut pas dire, selon lui, que toutes ces recrues ont reçu des instructions sur des cibles précises à attaquer une fois revenues dans leur pays.
"Aqpa, après avoir entraîné ces éléments, leur laisse la liberté de choisir leurs cibles et les moyens de s'y prendre", souligne-t-il.
La brance saoudo-yéménite d'Al-Qaïda s'assure ainsi, selon ce chercheur, une dimension planétaire pour ses actions qui menacent directement l'Occident.
"Une éventuelle revendication ne voudrait pas dire qu'il y ait eu une implication directe et une aide opérationnelle d'Aqpa", souligne aussi M. Bonnefoy.
Il n'en reste pas moins que le journal satirique français était présent sur une liste de cibles d'Aqpa.
Le magazine du groupe en anglais, "Inspire", lancé dans le but de susciter des vocations de "loup solitaire" à l'étranger, a appelé ses partisans à mener des attentats en France et inscrit en 2013 le directeur de Charlie Hebdo, Charb, sur sa liste de personnes à abattre.
Dès mars 2008, l'ancien chef d'Al-Qaïda Oussama ben Laden avait averti l'Europe qu'elle devrait "rendre des comptes" pour les caricatures du prophète Mahomet publiées dans les quotidiens danois et repris par Charlie Hebdo.