Lula, pictured next to his girlfriend Rosangela da Silva, told the crowd he would establish his innocence / AFP
The left-wing former leader, known as Lula, was greeted with rapturous applause from crowds of supporters as he walked out of the jail on Friday.
He was held in a prison in the city of Curitiba on corruption charges.
A judge ordered his release after a Supreme Court ruling that defendants should only be imprisoned if they have exhausted their appeal options.
The 74-year-old ex-president, who led Brazil between 2003 and 2010, is seen as a leftist icon in the country. As he left the prison, he pumped his fist in the air as a victory sign.
"I didn't think that today I could be here talking to men and women that during 580 days shouted good morning, good afternoon or goodnight, no matter if it was raining or 40 degrees [Celsius]," he told the crowds.
He also promised to prove his innocence, before hitting out at the "rotten side of the judicial system", which he accused of "working to criminalise the left".
Lula was favourite to win last year's presidential election but was imprisoned after being implicated in a major corruption scandal. The race was won instead by far-right candidate Jair Bolsonaro.
Criticising Mr Bolsonaro's economic policies, Lula vowed to keep fighting for impoverished Brazilians.
"People are hungrier, they have no jobs, people work for Uber or delivering pizzas on a bike," he added, specifically criticising insecure work and the gig economy.
After Lula's release, President Bolsonaro said the ex-president was "momentarily free, but guilty".
He asked supporters on Twitter "not to give ammunition to the scoundrel".
Lula will be barred from standing for office because of his criminal record.
He has consistently denied all the accusations against him and claims they are politically motivated.
"Our judicial battle continues, our focus is to get the legal case nullified," his lawyer Cristiano Zanin said.
For Lula's supporters, this feels like vindication - he's a politician who stirs emotions and those who back him feel that this has been a political witch-hunt from the very beginning.
There's no guarantee Lula will remain free forever - he may not win the appeals that are left - and he's also been accused of corruption in other cases which he will have to face justice for.
But with Lula now free, it will strengthen the left in Brazil - and harden the right. President Bolsonaro doesn't hide his disdain for Lula and millions of people agree - the anger towards Lula and the Workers Party is what propelled Mr Bolsonaro to power in the first place.
Justices voted to reinterpret the country's penal code in a decision issued on Thursday.
It overturns a three-year-old rule which mandated immediate prison time for convicted criminals after they lost their first appeal.
Brazil's corruption scandal, known as Operation Car Wash, initially centred on the state-run oil company Petrobras, but subsequently billions of dollars of bribes were uncovered - and dozens of high-profile business leaders and politicians were jailed.
The mandatory imprisonment rule was seen as helping prosecutors secure convictions and unravel the scandal by encouraging suspects to negotiate plea deals.
But critics claimed it violated Brazil's constitution, which states that no one can be deprived of their liberty without due process of law.
Lula was jailed in 2018 after being sentenced to more than 12 years in prison, later reduced to eight years and 10 months, for receiving a beachside apartment from an engineering company implicated in the Car Wash investigation.
Earlier this year, he was sentenced to another 12 years after being found guilty of accepting bribes in the form of renovation work at a country house from construction companies.