The three women, Maria Alyokhina, Yekaterina Samutsevich, and Nadezhda Tolokonnikova, were convicted in 2012 after staging a protest performance in a cathedral during Vladimir Putin's presidential campaign.
Alyokhina and Tolokonnikova spent 22 months in jail before being let out under a general amnesty in December, while Samutsevich received a suspended sentence.
However they continued to fight the ruling and the Supreme Court ordered in December that the verdict be reviewed.
The presidium also ruled that the original sentence of two years should receive a token reduction to one year and 11 months.
Also Read
The full original verdict had stated that the "punk prayer" that the women performed in the Cathedral of Christ the Saviour on February 17, 2012, was a gross violation of public order that "disrespected society" and was motivated by "religious hatred".
Lawyer Irina Khrunova said that the defence will still pursue the appeal to the European Court of Human Rights.
Meanwhile Alyokhina and Tolokonnikova, who have been on a whirlwind tour around the world since their release, were in New York, where they met with former Secretary of State Hillary Clinton and are scheduled to discuss their prison experience at a panel of the Women in the World summit tomorrow.