Charles Bandora arrived on a KLM commercial flight, landing at Kigali international airport in the early evening, Radio Rwanda reported.
The Norwegian officials accompanying Bandora handed him over to Jean-Bosco Siboyintore, head of the judicial unit responsible for tracking genocide suspects abroad, according to the New Times newspaper.
Charles Bandora, who is now in the hands of the police, is described as an influential member of the former ruling party MRND of the late president Juvénal Habyarimana. He is accused of participating in training of Interahamwe militia in Bugesera, eastern Rwanda, and of having supervised massacres in 1994. Rwanda requested his extradition in 2008.