Battisti left prison this morning after the court yesterday rejected his extradition and set him free after four years in jail. The judges were split with the decision agreed by six votes to three.
Battisti is accused of four murders and attempted murders at the end of the 1970s when some small far-left groups took to arms, as did the far right and secret service provocateurs.
He denies the charges.
An Italian court sentenced him in absentia to life imprisonment 18 years ago for the crimes.
A Brazilian court in 2009 agreed to extradite Battisti, but later ruled that the then-president Luiz Inacio Lula da Silva had the final say.
On the last day of his mandate, Lula rejected the extradition request, saying Battisti could be a victim of political persecution in Italy.
Battisti could also face other charges in Brazil. At the time of his arrest in 2007, he had fake papers and no visa.
He lived in France briefly in the 1980s and again from 1990 to 2007 and wrote several detective novels based in the Italian expatriate community.