Początki kariery

Karierę muzyczną zaczynał w czasach nauki w szkole, kiedy to śpiewał w szkolnych i kościelnych chórach. W tym czasie był członkiem Celebration Gospel Choir, z którym wydał album studyjny, a także lokalnego zespołu muzycznego Just 4 Music.

Na początku lat 90. przeniósł się do Stanów Zjednoczonych, gdzie w 1994 roku pod pseudonimem Kobra wydał swój debiutancki album studyjny zatytułowany Seeing Is Believing. W tym samym roku nawiązał współpracę z zespołem Rödelheim Hartreim Projekt i pojawił się gościnnie w utworze „Reime” z ich debiutanckiej płyty pt. Direkt aus Rödelheim z tegoż roku. Dwa lata później ukazał się drugi album studyjny duetu pt. Zurück nach Rödelheim, na którym znalazło się m.in. pięć piosenek z wokalem Naidoo.

W latach 1995 i 1998 występował jako jeden z głównych aktorów w musicalach Human Pacific i Pacific autorstwa Richarda Gepperta.

1997–1999

W 1997 opublikował debiutancki singiel „Freisein”, który nagrał w duecie z Sabriną Setlur. 30 maja 1998 wydał drugą płytę studyjną pt. Nicht von dieser Welt, która uzyskała wynik ponad miliona sprzedanych egzemplarzy oraz dotarła do pierwszego miejsca listy najczęściej kupowanych albumów w Niemczech, piątego w Austrii dwunastego w Szwajcarii. Na płycie znalazły się m.in. single „Führ mich ans Licht”, „20.000 Meilen”, tytułowy „Nicht von dieser Welt” i „Eigentlich gut” z gościnnym udziałem rapera Costy „Illmat!ca” Meronianakisa. W tym samym roku Naidoo pojawił się gościnnie na dwóch singla rapera: „I Got U Stripped” i „Skillz”.

W marcu 1999 zdobył niemiecką nagrodę muzyczną Echo w dwóch kategoriach: Debiut roku i Artysta roku, później odebrał także statuetkę Viva Comet Awards za wygraną w kategorii Najlepszy lokalny artysta oraz Europejską Nagrodę Muzyczną MTV dla najlepszego niemieckiego wykonawcy. W tym samym miesiącu wydał singiel „Sie sieht mich nicht”. Utwór został wykorzystany w ścieżce dźwiękowej niemieckiej wersji językowej filmu Asterix i Obelix kontra Cezar. Piosenka dotarła do drugiego miejsca listy przebojów w Niemczech, piątego w Szwajcarii i jedenastego w Austrii. W tym samym roku wydał pierwszy album koncertowy pt. Live zawierający nagrania „na żywo” zarejestrowane podczas trzech koncertów: w Mannheim w grudniu 1998 oraz w Rastatt i w Travemünde w lipcu tegoż roku. Oprócz tego pojawił się gościnnie w kilku utworach z płyty Sabriny Setlur zatytułowanej Aus der Sicht und mit den Worten von....

2000–2009

W marcu odebrał kolejną nagrodę Echo w kategorii artysta roku, był także nominowany do zdobycia statuetki za wygraną w kategorii Pop-rockowy singiel roku (za utwór „Siehst du mich”). Pod koniec czerwca wydał swój nowy singiel „Seine Strassen”. W tym samym roku nagrał także utwór „Alles” w duecie z Sabriną Setlur. W ciągu kolejnych miesięcy pojawił się gościnnie na singlach kilku innych niemieckojęzycznych artystów: w utworze „Über sieben Brücken musst du gehen” szwajcarskiego piosenkarza Erkana Akiego, „Jeanny” niemieckiego zespołu Reamonn i „Way to Mars” producenta M2. W listopadzie 2000 razem z zespołem Söhne Mannheims wydał album pt. Zion.

25 marca 2002 wydał trzeci solowy album studyjny pt. Zwischenspiel/Alles für den Herrn, który dotarł do pierwszego miejsca listy najczęściej kupowanych płyt w Niemczech i Austrii oraz trzeciego w Szwajcarii. Krążek był promowany przez single „Lied (Du Nur, Du)”, „Wo willst du hin?”, „Abschied nehmen”, „Bevor du gehst” i „Wenn ich schon Kinder hätte”, który został nagrany z gościnnym udziałem Michaela „Curse’a” Kurtha. W tym samym roku ponownie zdobył Europejską Nagrodę Muzyczną MTV dla najlepszego niemieckiego wykonawcy, a także udzielił swojego głosu postaci Kapiszona w niemieckiej wersji językowej filmu Miasto Boga oraz nawiązał współpracę z raperem Robertem F. Diggsem Juniorem „RZA”, pojawiając się gościnnie w dwóch jego singlach: „I’ve Never Seen” oraz „Ich kenne Nichts (Das so schön ist wie du)”, który dotarł do pierwszego miejsca list przebojów w Niemczech, drugiego w Austrii i trzeciego w Szwajcarii.

W 2003 był nominowany do zdobycia trzech nagród Echo w kategoriach: Najlepszy teledysk roku (za klip do „Bevor du geht’s”), Artysta roku i Producent roku, jednak ostatecznie nie zdobył żadnej statuetki. W czerwcu ukazała się jego druga płyta koncertowa zatytułowana Alles gute vor uns (Live on Tour). W tym samym roku nagrał singiel „Tu me manques” ze szwajcarskim raperem Andresem „Stressem” Andreksonem, a także zdobył nominację do Europejskiej Nagrody Muzycznej MTV dla najlepszego niemieckiego wykonawcy.

W 2004 nagrał singiel „Tage & Stunden” w duecie z piosenkarką Bintią Bangurą. W marcu odebrał nagrodę Echo za wygraną w kategorii Pop-rockowy singiel roku (za „Ich kenne Nichts”), był nominowany również do zdobycia statuetki w kategorii Artysta roku. W czerwcu wraz z zespołem Söhne Mannheims wydał ich drugą płytę studyjną pt. Noiz. W 2005 ukazała się nowa płyta zespołu pt. Power of the Sound. Na początku listopada 2005 wydał kolejny singiel, „Dieser Weg”, który zwiastował jego czwarty solowy album studyjny zatytułowany Telegramm für X wydany pod koniec miesiąca. Krążek zadebiutował na pierwszym miejscu listy najczęściej kupowanych płyt w Niemczech, Szwajcarii i Austrii oraz zdobył tytuł czterokrotnej platynowej płyty w Niemczech dzięki uzyskaniu wyniku ponad 800 tys. sprzedanych kopii. Pozostałymi singlami z albumu zostały single „Bist du am leben interessiert” (nagrany z Anthonym Malcolmem Wolzem), „Zeilen aus Gold” i „Was wir alleine nicht schaffen”.

W marcu 2006 odebrał statuetkę Echo z wygraną w kategorii Artysta roku, był nominowany również do zdobycia nagrody za Krajowy/Międzynarodowy przebój roku (za utwór „Dieser Weg”). W lipcu ukazał się jego nowy singiel „Danke”, który został napisany w hołdzie reprezentacji Niemiec w Mistrzostwach Świata w Piłce Nożnej organizowanych w Berlinie. Piosenka dotarła do pierwszego miejsca listy przebojów w kraju. W tym samym roku został wybrany Mężczyzną roku w plebiscycie czytelników niemieckiego wydania magazynu Men’s Health. Niedługo potem zdecydował się na krótką przerwę w działalności artystycznej, która trwała do 2007. W tymże roku otrzymał nominację do nagrody Echo w kategorii Najlepszy występ na żywo, której ostatecznie nie wygrał.

W 2008 razem z zespołem Söhne Mannheims wziął udział w koncercie MTV Unplugged, nagranie z którego zostało wydane w formie płyty koncertowej zatytułowanej Wettsingen in Schwetzingen – MTV Unplugged wydanej w połowie września tego samego roku. Album zapewnił piosenkarzowi nominacje do nagród Echo w kategoriach Najlepsza produkcja DVD i Najlepsza grupa/współpraca. W 2009 ukazała się nowa płyta grupy pt. Iz On, z którą piosenkarz wyruszył w trasę koncertową. W tym samym roku premierę wydał kolejny solowy album studyjny pt. Alles kann besser werden. Trzypłytowe wydawnictwo promowały single „Bitte hör nicht auf zu träumen”, „Ich brauche dich” oraz tytułowy „Alles kann besser werden”.

2010–2019

W 2010 odebrał kolejną statuetkę Echo za wygraną w kategorii artysta roku. Był nominowany również do zdobycia nagrody w kategorii Najlepszy Występ na Żywo, a także po raz czwarty uzyskał nominację do Europejskiej Nagrody Muzycznej MTV dla najlepszego niemieckiego wykonawcy. W tym samym roku wydał koncertową wersję płyty pt. Alles kann besser werden.

W latach 2011-2012 był jednym z mentorów programu The Voice of Germany. W 2012 nawiązał współpracę z raperem Koolem Savasem, z którym reprezentował Badenię-Wirtembergię w Bundesvision Song Contest pod nazwą Xavas. W finale konkursu wykonali utwór „Schau nicht mehr zurück”, z którym ostatecznie wygrali festiwal. Po wygranej w konkursie wydali swoją pierwszą wspólną płytę studyjną zatytułowaną Gespaltene Persönlichkeit, która była promowana przez single „Schau nicht mehr zurück”, „Lass nicht los”, „Die Zukunft trägt meinen Namen” i „Wenn es nacht ist”.

31 maja 2013 wydał kolejną solową płytę studyjną pt. Bei meiner Seele, która promowana była przez single „Der Letzte Blick” i tytułowy „Bei meiner Seele”. W 2014 otrzymał nominacje do nagród Echo w dwóch kategoriach: Najlepszy artysta pop-rockowy i Najlepszy teledysk (za klip do „Bei meiner Seele”). W tym samym roku wydał kolejny album koncertowy pt. Hört, Hört! (Live von der Waldbühne).

19 listopada 2015 poinformowano, że będzie reprezentował Niemcy w 61. Konkursie Piosenki Eurowizji organizowanym w Sztokholmie. Wewnętrzny wybór piosenkarza na przedstawiciela kraju spotkał się z mieszanymi opiniami zarówno fanów konkursu, jak i samych mieszkańców Niemiec, co podyktowane było m.in. kontrowersyjnymi poglądami politycznymi artysty. W ciągu doby od ogłoszenia nazwiska niemieckiego przedstawiciela, internetową petycję skierowaną do krajowego nadawcy publicznego w celu przekonania go do zmiany reprezentanta podpisało ponad 10 tys. osób. Całą sytuację skomentował sam Naidoo, który przyznał, że „wierzy w wolność słowa” oraz że „to przykre, że ludzie, którzy go nie znają, oceniają go na podstawie kilku oświadczeń bez rzeczywistego znaczenia”. 21 listopada stacja poinformowała o wycofaniu się Naidoo z udziału w konkursie.