André Naujoks wurde in Hamburg geboren und studierte dort an der Joop van den Ende Academy. Es folgten Engagements in Musicals wie Spring‘s Awakening an den Vereinigten Bühnen Wien, Victor/Victoria sowie Vom Geist der Weihnacht. Mit den Schauspielbühnen Stuttgart ging er mit Produktionen wie Blue Jeans auf Tournee und gastierte dort anschließend bei Kiss Me, Kate sowie als Steve in der Musical-Story My Life and Pink Floyd. In Die Schönheitsklinik – die Schlagerrevue spielte André Naujoks den Hamburger Jung Manfred Schreiber und war zudem mit Mamma Mia! (Stage Entertainment) in der Show von Carmen Nebel zu Gast. In Saturday Night Fever (Luzern) spielte André Naujoks die Rolle des Bobby C und wirkte anschließend bei den Thunerseespielen im Ensemble und als Tybalt (Cover) in Romeo und Julia mit. Kurz darauf war André Naujoks in Chicago (Stage Entertainment), Sunset Boulevard (Schlossfestspiele Ettlingen) und Evita (VBW) zusehen. Seine letzten Engagements waren Ghost (Landestheater Linz sowie Stage Entertainment), Jesus Christ Superstar im Raimund Theater Wien sowie Der Medicus und Die Päpstin (Fulda).