"We're deeply concerned about the plight of the nurses," Bush told reporters after meeting with Bulgarian President Georgi Parvanov, whose government has been working with the European Union and the United States to gain the medics' freedom.
"They should be released and they should be allowed to return to their families," Bush said on the final stop of his European tour.
Bulgaria's leaders were appealing to Bush for U.S. help in freeing the five Bulgarians and a Palestinian doctor sentenced to death in Libya for allegedly infecting hundreds of children with the virus.
Detained since 1999, the six are accused of intentionally infecting about 400 children with HIV at a hospital in Benghazi. All deny the charge.
The six medical workers were sentenced to death twice, in 2004 and again in 2006 following a court appeal. Libyan court officials said they confessed, but some of the nurses have since said they confessed under beatings and torture. They all say they are innocent.
On Sunday, German Foreign Minister Frank-Walter Steinmeier - whose country holds the EU's rotating presidency - traveled to Libya to try to win their release. Steinmeier was accompanied by Benita Ferrero-Waldner, the EU's external relations commissioner.
"The German EU presidency and the European Commission are striving to exert the necessary influence on Libya so that the individuals in question are released as soon as possible," the German government said Monday in a statement.
Steinmeier and Ferrero-Waldner visited the five nurses and the Palestinian doctor in Tripoli on Monday.
"The whole of Europe is in solidarity" with the nurses and the doctor, Steinmeier said, according to the Foreign Ministry in Berlin, adding that "we found them in tense but steadfast spirits."
"This meeting was very moving," he added. "We are not leaving the prisoners alone. They can reckon firmly with our support. We will do everything to achieve their release. Europe remains at their side."
Steinmeier also said the Europeans were working "to improve the lot of the HIV-infected children in Benghazi."
On Sunday, Steinmeier said he had an emotional visit with some of the children and their parents and doctors.
Expert witnesses at the medics' trial testified that HIV was rampant at the Benghazi hospital and that the children were infected before the Bulgarians began working there in the late 1990s.
The six are awaiting another appeal of their convictions and death sentences before Libya's supreme court.
Parvanov thanked Bush for his support of his government's efforts "to achieve a just sentence for our countrymen in Libya, meaning their release."
Their plight has been a major issue for Bulgarians, who have staged numerous protests and rallies over the years to call for their release.