Hailemariam Desalegn said a new detention centre will comply with international standards
Ethiopia's government has denied that all political prisoners will be freed, saying that only some imprisoned politicians will be pardoned.
An aide to the prime minister said a mistranslation led to him being quoted as saying that all political prisoners would be freed to promote dialogue.
The prime minster also said a detention centre, allegedly used as a torture chamber, would be shut.
Ethiopia has been hit by a wave of political unrest in recent years.
Amnesty International welcomed the initial announcement, saying it could signal "the end of an era of bloody repression in Ethiopia" - although it warned that the closure of the Maekelawi detention centre should not be used to "whitewash" the "horrifying" events which took place under its roof.
Ethiopia has always denied that there were any political prisoners in the country, as alleged by human rights and opposition groups.
In a statement on Thursday, Prime Minster Hailemariam Desalegn's office said that "some members of political parties and other individuals that have been allegedly suspected of committing crimes or those convicted will be pardoned or their cases interrupted based on an assessment that will be made so as to establish a national consensus and widen the political sphere".
It remains unclear how many people will be freed, or when.
One of the main opposition groups, the Ethiopian Federal Democratic Unity Forum (Medrek), said the government often engaged in "face-saving" measures and tried to "buy time" when it was "cornered".
Medrek was, nevertheless, prepared to enter into dialogue with the government, if it was genuine and the talks led to free and fair elections, said the group's deputy leader, Beyene Petros.
Who are the prisoners?
Those held in jails across the country include opposition activists from the Amhara and Oromia regions, which were at the centre of anti-government protests in 2015 and 2016, and journalists who have criticised the government, says BBC Ethiopia correspondent Emmanuel Igunza.
The prisoners also include UK citizen Andargachew Tsege, who was seized in 2014 when changing planes in Yemen and forced to go to Ethiopia, where he had been sentenced to death in absentia for his political activities against the state.
It is difficult to know exactly how many politicians have been imprisoned, but our correspondent estimates that about 1,000 are held under the country's anti-terrorism proclamation, including high profile leaders from the opposition.
However, there are another 5,000 cases still pending, made up of those arrested after a state of emergency was declared in October 2016, he adds.
Will they actually be released?
The government has given no timeline on the release of the prisoners, including those still awaiting trial.
Our reporter notes a number of cases have political backgrounds, but are also linked to groups the government considers to be terrorists. Nineteen people linked to Ginbot 7 - deemed a terror group - were sentenced to prison terms just this week.
Thousands have been detained since anti-government protests broke out
Whether they will all be released remains to be seen.
Any dialogue would have to include legitimate opposition groups like the Oromo Federalist Congress, whose leaders would have to be freed to fully participate in the process, our correspondent says.
What about the detention centre?
As well as releasing the prisoners, Mr Hailemariam announced the closure of Maekelawi - a detention facility in the capital, Addis Ababa, which Amnesty International described as a "torture chamber used by the Ethiopian authorities to brutally interrogate anybody who dares to dissent, including peaceful protesters, journalists and opposition figures".
"A new chapter for human rights will only be possible if all allegations of torture and other ill-treatment are effectively investigated and those responsible brought to justice," Amnesty International added.
The government strongly denies the torture allegations, but it has now decided the prison will become a "modern museum" - a move the privately-owned Addis Standard newspaper called for in an editorial in 2016.
A new detention centre will be opened, Mr Hailemariam said, which would comply with international standards.
Our correspondent says detentions have always been a major concern. In December, social media users staged a day of action to remember those held behind bars.
But this decision comes hot on the heels of a meeting between the parties which make up the ruling Ethiopian People's Revolutionary Democratic Front (EPRDF) coalition.
Over the past months, infighting within the coalition, which has been in power for more than 25 years, has led the prime minister to acknowledge the need for change.
The Oromo Peoples' Democratic Organization and the Amhara National Democratic Movement, which are part of the coalition, have been pushing for increased political space and the "respect of their people" following the massive anti-government demonstrations that have been witnessed in the country.
Who is Hailemariam Desalegn?
A trained engineer, Mr Hailemariam took the reins of power in 2012, after the death of Meles Zenawi, who had ruled since 1991.
However, while the former deputy prime minister was a close ally of Mr Meles, he struggled to gain approval of the other EPRDF leaders in order to assume his new role.
He is not known for tolerating dissent well, despite statements to the contrary, his critics say.
In 2016, he blamed "anti-peace forces" for the violence in the Oromia region, a year after he told the BBC that bloggers and reporters arrested were not real journalists and had terror links.