Rwanda’s President Paul Kagame and Uganda’s Yoweri Museveni were once close allies but their relations have turned deeply hostile.
Kigali and Kampala signed a deal in August last year to improve political and economic relations, but progress has since been slow.
In the deal signed on Sunday by Kagame and Museveni in the Angolan capital Luanda, the two sides agreed to “the release of the national citizens of each country.”
But the two leaders, who met at a summit hosted by Angolan President Joao Lourenco, and alongside Democratic Republic of Congo President Felix Tshisekedi, pledged to take “steps towards peace, stability, good neighbourliness and restoring mutual trust.”
They also agreed the two sides would meet again on February 21 for more talks at a common border post between the nations.
“Both parties must refrain from all factors that may create the perception of supporting, financing, training and infiltration of destabilising forces in their neighbour’s territory,” the agreement read.
Rwanda abruptly closed the border with its northern neighbour in February last year, severing a major economic land route.
The country has also accused Uganda of abducting its citizens and supporting rebels seeking to overthrow its government.
Then in May Ugandan police accused Rwandan soldiers of entering the country and killing two men — a claim which Kigali denied.