Trujillo begann im Alter von sechs Jahren Klarinette und später Saxophon zu spielen. Seit 1980 lebt er in Amsterdam, wo er zwischen 1989 und 1994 am Conservatorium van Amsterdam bei Tim Armacost (Saxophon) und Misha Mengelberg (Arrangement) studierte und 1994 sein Master-Diplom erhielt.
Trujillo ist langjähriges Mitglied im Fusion-Quartett The Ploctones, aber auch bei Fra Fra Sound, The Preacher Men, Sven Schusters Shooster und dem großformatigen New Cool Collective, mit denen er mehrere Alben einspielte und international auf Tournee war. In den letzten Jahren trat er beim North Sea Jazz Festival, beim Standard Bank Jazz Festival in Südafrika und beim Tokyo Jazz Festival in Japan auf. Außerdem arbeitete er viele Jahre lang als Hausmusiker für die NTR-Sendung Mijke & Co Live. Dort hatte er die Möglichkeit, mit internationalen Stars wie Oleta Adams, Dr. Lonnie Smith, Gregory Porter, George Duke und Chris Potter aufzutreten. Seit 2014 ist er künstlerischer Leiter des Amsterdam Funk Orchestra. 2010, 2011 und 2013 wurde er (mit den Ploctones und mit Ob6sions) für den Edison Award nominiert. Mit dem Pianisten Tico Pierhagen arbeitete er im Duo. Er ist auch auf dem Album Songs & Jives der Weltmusik-Gruppe Sefuba zu hören.
