The agreement was signed in Kigali in 2021 and approved by the Maputo government in March last year, around the same time the Rwandan senate ratified the treaty.
"This agreement will allow Mozambique's justice administration bodies and Rwanda's justice administration bodies to exchange information on citizens," Justice Minister Helena Kida told parliament.
She warned that Mozambique would not "allow those who have committed heinous crimes to hide in our house.
"Our intention is not to mistreat those who do well, but we are not going to embrace those who are criminals," she said.
Rwandan refugees and asylum seekers in Mozambique have in the past expressed concern that the treaty would be used to hound dissidents seen as opposed to the Kigali government.
President Paul Kagame's government is often accused of targeting opponents in exile, a charge it has always denied.
"Even without the agreement" Rwandan citizens "suffer persecution and murder in our country," Catarina Salomao, a lawmaker from the main opposition party RENAMO said.
Echoing this, another opposition lawmaker Elias Impwiri denounced the treaty as a "political ploy by Kigali to force the inhumane trial of political opponents."
Last year, Human Rights Watch (HRW) reported that at least three Rwandans have disappeared or been killed in Mozambique under "suspicious circumstances" since 2021, while others escaped kidnappings.
A former Rwandan lieutenant was shot dead in a Maputo suburb in 2021, and in 2012 the body of the former head of Rwanda's Development Bank was found floating at sea off the capital.
The global rights watchdog also found that several Rwandan refugees said they were "threatened by embassy officials and told they would die if they did not fall in line."
President of the Rwandan Refugee Community in Mozambique, Cleophas Habiyareme, called for "legal mechanisms to be established to help ascertain whether an extradited citizen has committed a crime or not, before they are extradited."
The two African countries enjoy close diplomatic ties.
In 2021, more than 2,000 troops from Rwanda arrived to help Mozambique's forces fight an Islamist insurgency in the country's gas-rich northern province of Cabo Delgado.
The opposition MDM party argued the agreement should not "serve as a bargaining chip or to thank the government for Kigali's help in combating terrorism in Cabo Delgado province."
Several thousand Rwandan refugees live in Mozambique, according to United Nations figures.
Most settled in the country after the 1994 Rwandan genocide, which cost the lives of some 800,000 people.
Kagame's rebels defeated the regime that launched the killing and he has been president ever since, and his rule has become increasingly authoritarian.
MAPUTO —Mozambique's parliament ratified an extradition treaty with Rwanda on Thursday despite fears that Kigali will use it to persecute exiled dissidents.