Na swoich pierwszych igrzyskach olimpijskich 1996 w Atlancie był jednym z głównych faworytów do złotego medalu. Turniej zakończył z 6 medalami (2 złote, 1 srebrny, 3 brązowe). W wieloboju walczył jak równy z równym z mistrzem świata – Chińczykiem Li Xiaoshuangiem, jednak w decydującym momencie zmarnował swój środkowy bieg, tym samym zdobywając wicemistrzostwo olimpijskie, z niewielką stratą do Li Xiaoshuanga.
Gdy wielu kwestionowało zaangażowanie oraz poziom sprawności Niemowa, on w dalszym ciągu odnosił sukcesy na zawodach międzynarodowych. W 2000 roku z powodu licznych kontuzji barku, obawiano się o jego wyniki podczas igrzysk olimpijskich 2000 w Sydney. Turniej zakończył z 6 medalami (2 złote, 1 srebrny, 3 brązowe).
Igrzyska olimpijskie 2004 Pomimo problemów z kontuzją Niemow pojechał na igrzyska olimpijskie 2004 w Atenach, jako jeden z liderów odmłodzonej drużyny Sbornej. Choć Niemow już nie był w najlepszej formie, prezentował wysoki poziom podczas turnieju, stał się także bohaterem kontrowersji sędziowskich. W ćwiczeniach drążków (wykonał trzy warianty Tkaczowa oraz jeden Giengera), sędziowie przyznali mu łączną notę 9,725, co dawało mu wówczas 3.