Andrei Nikitenko begann seine Karriere als Eishockeyspieler in seiner Heimatstadt in der Nachwuchsabteilung von Gasowik Tjumen, für dessen Profimannschaft er in der Saison 1997/98 sein Debüt in der Superliga gab. In der folgenden Spielzeit stieg der Center mit seiner Mannschaft in die Wysschaja Liga, die zweite russische Spielklasse, ab. Er selbst blieb jedoch in der Superliga und spielte in den folgenden drei Jahren für Ak Bars Kasan, mit dem er 2000 und 2002 jeweils Vizemeister wurde. In seinem ersten Jahr in Kasan kam er zudem zu zwei Einsätzen für den Zweitligisten Neftjanik Leninogorsk.
Während des Expansion Draft am 17. Juni 2013 wurde Nikitenko von Admiral Wladiwostok ausgewählt.[1]
Im Mai 2014 wurde er vom KHL-Rückkehrer HK Lada Toljatti für zwei Jahre verpflichtet, ehe er seine Karriere im April 2016 beendete.
International
Für Russland nahm Nikitenko an der U20-Junioren-Weltmeisterschaft 1999 teil, bei der er mit seiner Mannschaft Weltmeister wurde. Zu diesem Erfolg trug er mit fünf Torvorlagen in sieben Spielen bei.
