1986 marque un tournant dans la carrière de Patrice Sanahujas car il y rencontre deux jeunes auteurs, Philippe Leclerc et Alain Paris, qui lui ouvriront de nouveaux horizons de travail. Le premier avait participé au Roi et L'Oiseau de Paul Grimault et collabore alors en tant qu'assistant-réalisateur au futur Gandahar de René Laloux. Ensemble, ils se lancent dans un projet de court métrage d'animation intitulé La Nuit d'Arzawa, court métrage qui n'aboutira pas mais qui offrira à Patrice Sanahujas une première expérience dans ce domaine.
Quant à Alain Paris, l'amitié qui se noue entre ce jeune écrivain historien de formation et le dessinateur est très certainement le déclencheur qui poussera ce dernier dans le milieu de l'illustration.
A partir de 1987, Patrice Sanahujas effectue deux couvertures pour les éditions Corps 9 Andromède avant de travailler pour la célèbre collection Anticipation du Fleuve Noir, sa première illustration pour cette collection étant celle du Dieu de la Guerre de son ami Alain Paris. Vingt-neuf dessins verront le jour au Fleuve Noir entre 1989 et 1994, dont dix pour des oeuvres de Alain Paris, Patrice Sanahujas illustrant par la suite des auteurs aussi célèbres que P-J Hérault et Jean-Pierre Garen à partir de 1992 (qui représentait les meilleurs ventes de cette collection).
En 1989, il entre en contact avec Gérard Klein, le directeur de collection du Livre de Poche, et produit trois couvertures pour cette maison d'édition, illustrant les textes de grands auteurs de la littérature S-F américaine : Philip K. Dick (Ubik), Thomas Disch (Génocide) et John Brunner (Sur l'Onde de Choc).
C'est en 1991 que l'éditeur Claude Lefrancq se met à la recherche d'un nouveau dessinateur pour illustrer la réédition des aventures de Bob Morane, le célèbre aventurier créé par Henri Vernes en 1953. C'est tout naturellement qu'il se tourne vers Patrice Sanahujas, dont il avait édité l'adaptation BD du Monde Perdu d'Arthur Conan Doyle. L'artiste s'attele avec joie à ce travail qui le replonge 25 années en arrière, à l'époque où il dévorait les aventures de ce héros publiées par Marabout et illustrées par Pierre Joubert.