Father Wenceslas Munyeshyaka and the former prefect Bucyibaruta had been held since 20 July at the request of the International Criminal Tribunal for Rwanda (ICTR).
The ICTR wished that they be maintained in detention until a chamber, designated for this purpose, comes to a conclusion about the transfer, or not, of their cases to French courts.
The UN tribunal, which must finish its first instance trials by December 2008, has chosen to transfer certain cases to national courts.
France agreed to try the two accused but it is awaiting the go ahead of the ICTR judges.
By releasing Munyeshyaka and Bucyibaruta, the Court of Appeal had estimated that their arrest and their detention violated, in particular, the principle of presumption of innocence.
At the office of the prosecutor of the ICTR, they are pointing out that an appeal can be filed until 8 August.
Munyeshyaka and Bucyibaruta have been for some years under judicial supervision in France. This measure remains in force.
© Hirondelle News Agency