Mr Mandela will celebrate his 90th birthday later this year
US Secretary of State Condoleezza Rice has asked for "embarrassing" travel restrictions on Nelson Mandela and South African leaders to be lifted.
A bill has been introduced in the US Congress to remove from databases any reference to South Africa's governing party and its leaders as terrorists.
The African National Congress (ANC) was designated as a terrorist organisation by South Africa's old apartheid regime.
At present a waiver is needed for any ANC leaders to enter the country.
"It is frankly a rather embarrassing matter that I still have to waive in my own counterparts - the foreign minister of South Africa, not to mention the great leader, Nelson Mandela," Ms Rice told lawmakers in Washington.
Last week, Howard Berman, chairman of the House Committee on Foreign Affairs, who introduced the bill said it was "shameful" that the United States still treated the ANC this way.
"Amazingly, Nelson Mandela still needs to get a special waiver to enter the United States based on his courageous leadership of the ANC. What an indignity. This legislation will wipe it away," he said.
South Africa's apartheid government banned the ANC in 1960, imprisoning or forcing into exile its leaders.
Mr Mandela, who turns 90 this year, was released in 1990 after spending 27 years in prison.
He then became the country's first post-apartheid-era president, before retiring after serving one term in office.
He appears to be in reasonable health, but now makes far fewer public appearances.
Nelson Mandela has been classified as a terrorist since the time of Apartheid in South Africa 
Nelson Mandela has officially been taken off the US list of terrorists by the United States government. This comes after a statement by Condoleezza Rice, the US Secretary of State, who said that it was a "rather embarrassing matter that I still have to waive in ... the great leader Nelson Mandela," back in April.

The ruling, which also applied to all members of the African National Congress means that Mandela can travel to the United States without being approved by the Secretary of State.

Nelson Mandela has recently been in the media due to his upcoming 90th birthday. As part of the celebrations, a concert was held in Hyde Park, attended by many influential politicians, including Bill Clinton, former US president.

Nelson Mandela was a campaigner against apartheid who served one term as president of South Africa.


Last week the government of North Korea was removed from the list of State Sponsors of Terrorism. This announcement was made as a reward to North Korea for turning over all documents related to its controversial nuclear program. Pyongyang turned over to China documents related to its plutonium core and waste activities.