A Katuku Tshimanga own goal and Oleksandr Aliyev's strike saw Anzi enjoy an unexpectedly comfortable passage to the last 16, where they will face AZ Alkmaar.
Anzhi's European journey has come as a surprise after being stripped of most of their big-name players in recent months following the decision of owner Suleyman Kerimov to drastically reduce the club's operating budget.
The exit of stars such as Samuel Eto'o, Willian, Christopher Samba, Lacina Traore and Igor Denisov has had a dramatic affect on Anzhi's domestic fortunes, with the club bottom of the Russian league after failing to win any of their 19 games so far.
Yet the situation has not been quite so bleak in Europe, with two wins and two draws in the group stage enough to see Anzhi progress to the knockout stage.
A goalless stalemate in the first leg did not augur particularly well but Anzhi set to their task with purpose in the opening half, Aliyev and Fedor Smolov both going close as Genk, who reached the knockout phase after topping Group G with four wins and two draws, struggled to get going.
Genk's lack of application can perhaps be explained by an unsettled few days at the club following the departure of coach Mario Been.
The Dutchman left in the wake of Sunday's 2-0 home defeat by Waasland-Beveren, with Emilio Ferrera appointed his successor.
The weekend reverse left Genk down in sixth in the Belgian league, well out of the title scrap, and their lack of confidence was laid bare on Thursday as Ferrera failed to rally his troops.
Jeroen Simaeys saw a decent header saved by Mihail Kerzhakov on a rare attack by the home side early in the second half, but it was the Russians making most of the running and it came as no surprise when they took the lead in the 64th minute as Tshimanga turned Aliyev's centre into his own net.
Genk's response to going behind was conspicuous by its absence and Anzhi duly profited with 71 minutes on the clock as Smolov played in Aliyev and the striker did the rest with a cool finish.
The only blot on Anzhi's night came with nine minutes remaining when Rasim Tagirbekov was needlessly sent off for aiming a volley of abuse at the referee after committing a foul.