Senators authorised $50 billon (£25bn) for PEPFAR, the President's Emergency Plan for AIDS Relief, by 80 votes to 16.
The bulk of the money is for HIV prevention and AIDS treatment, but there are substantial sums to fight TB and malaria. Countries in Africa and the Carribean will benefit.
Republican Senator Gordon Smith and Democratic Senator Kerry attached an amendment to a bill repealing current US immigration law.
At present any foreign national who tests positive for HIV is "inadmissible," meaning he is barred from permanent residence and even short-term travel in the United States.
There are waivers available to this rule, but obtaining them has always been difficult.
The ban originates from 1987, when fear about the spread of the disease led US officials to require anyone with HIV to declare their status and apply for a special visa. It became law in 1993.
As a result of the Senate vote the US Secretary of the Department of Health and Human Services can now lift the HIV ban.
It is unclear if President Bush’s administration will take action or allow the new President’s team to make the changes when they take office in January.
Changes to for PEPFAR will need to be discussed with the House of Representatives as they approved the legislation earlier this year.
The current PEPFAR programme has disbursed $15bn (£7.68bn) over five years and is to end in September.
"We applaud the Senate for rejecting this unjust and sweeping policy that deems HIV+ individuals inadmissible to the United States," said Joe Solmonese, president of Human Rights Campaign.
"Congress has finally moved to end the HIV ban, a ban based on myth and misinformation," said Rachel Tiven, executive director of Immigration Equality.
"For 20 years, the United States has barred HIV-positive travellers from entering the country even for one day."
The United States is one of 13 countries in the world, including Iraq, Saudi Arabia, and Sudan, that bans entry to individuals who are HIV-positive.
Last month the European Commissioner for Justice raised the ban with Michael Chertoff, US Secretary of Homeland Security.
Jacques Barrot asked for "information on the reasons why individuals carrying HIV are excluded from using the US Visa Waiver Programme."
MEPs have kept pressure on the Commission over the issue as the EU is in negotiations with the US authorities to secure visa-free travel (a visa waiver) for EU citizens from all 27 member states.
In May the European Parliament passed a resolution demanding the ongoing negotiations include the exclusion of Europeans with HIV from the visa waiver programme, and ensure equal treatment of all EU citizens.
The Commission says there are no objective reasons for a travel ban for HIV infected persons.
Earlier this year the Joint United Nations Programme on HIV and AIDS (UNAIDS) stated:
"There is no need to single out HIV for specific consideration as an exclusion criterion."
UN chief Ban Ki Moon has called for an end to discrimination against people with AIDS, including travel restrictions imposed on them by some countries.
"I call for a change in laws that uphold stigma and discrimination, including restrictions on travel for people living with HIV," he said last month at the opening of a two-day, high-level meeting in the General Assembly on UN targets, set in 2001 to roll back the disease worldwide.
"Halting and reversing the spread of AIDS is not only a goal in itself, it is a prerequisite for reaching almost all the others (poverty-reduction Millenium Development Goals by 2015)," he added.
He said that 60 years after the Universal Declaration of Human Rights was adopted, "it is shocking that there should still be discrimination against those at high risk, such as men who have sex with men, or stigma attached to individuals living with HIV."
According to UNAIDS, the global standard-bearer in the fight against HIV, 74 countries are subjecting HIV carriers to restrictive measures, including a mention of the disease on their passports.