"Two Lithuanian citizens, Yevgeny Mataitis and Aristidas Tamosaitis, have been returned to Lithuania and are currently on their way to their families," Jonas Vytautas Zukas, a presidential advisor, told reporters.
As part of the operation at a border checkpoint, two Russians jailed for espionage in Lithuania were handed over two Russia after being pardoned by President Gitanas Nauseda.
Darius Jauniskis, the director of the Lithuanian State Security Department (VSD), said the exchange took place at Friday noon.
Mataitis and Tamosaitis were convicted of spying for Lithuania and jailed in Russia in 2016.
Tamosaitis was sentenced to 12 years in prison by a Moscow court. A Kaliningrad court handed a 13-year prison sentence to Mataitis, a dual Lithuanian-Russian citizen.
Frode Berg, the Norwegian sentenced in Russia to 14 years in prison for espionage, was handed over to Norway's embassy in Vilnius on Friday.