Agnes Uwimana Nkusi and Saidati Mukakibibi to four and three years from 17 and seven years respectively.
Nkusi, editor of the Umurabyo newspaper, was last year convicted of defamation, causing divisions and denying Rwanda's 1994 genocide.
Mukakibibi, the publication's reporter, was found guilty of inciting civil disobedience.
"We welcome the acquittal on charges of genocide denial and divisionism as well as the sentence reductions, but we will continue to explore options to clear their names fully," said lawyer Nani Jansen represented the journalists for the London-based Media Legal Defence Initiative.
Rwanda’s entire batch of media laws are being overhauled and new access to information statutes are being enacted.
The new rules were passed by Rwanda’s parliament earlier this week are expected to be signed by President Paul Kagame by mid-2012.
Acting Director of Rwanda’s Media High Council, Emmanuel Mugisha, says the laws are not the primary problem facing Rwandan journalists.
“What Rwanda lacks is not free press, it’s professionalism," he says. "If one came up with a true story covering the truth of the matter, I can assure you Rwanda is one of the best grounds where they may even reward a journalist who has unveiled a story which is going to show the government or the decision makers any wrong.”