US Secretary of State John Kerry and a Yemeni intelligence official said Luke Somers, 33, and South African Pierre Korkie were shot by their kidnappers shortly after the raid began in the arid Wadi Abadan district of Shabwa, a province in southern Yemen long seen as one of al Qaeda's most formidable strongholds.
Kerry said the operation, the second attempt to free Somers in 10 days, had only been approved because of information that the American's life was in imminent danger.
However, the Gift of the Givers relief group, which was trying to secure Korkie's release, said it had negotiated for the teacher to be freed and had expected that to happen on Sunday and for him to be returned to his family.
Al Qaeda in the Arabian Peninsula (AQAP) is seen by Washington as one of the movement's most dangerous branches. The United States has worked with the Yemeni government and via drone strikes to attack its leadership in southern and eastern parts of Yemen.
"The callous disregard for Luke's life is more proof of the depths of AQAP's depravity, and further reason why the world must never cease in seeking to defeat their evil ideology," President Barack Obama said in a statement.
He said he had authorised the attempted rescue and said the United States would "spare no effort to use all of its military, intelligence and diplomatic capabilities to bring Americans home safely, wherever they are located".
Somers was moved from the scene of the rescue attempt but died later from his wounds, a senior official in the Yemeni president's office said.
Gift of the Givers said on its website: "We received with sadness the news that Pierre was killed in an attempt by American Special Forces, in the early hours of this morning, to free hostages in Yemen."
It added: "The psychological and emotional devastation to (Korkie's wife) Yolande and her family will be compounded by the knowledge that Pierre was to be released by al Qaeda tomorrow ... Three days ago we told her 'Pierre will be home for Christmas'."
A South African government spokesman declined to comment.
There was no new information about three other hostages, a Briton, a Turk and a Yemeni, who had previously been held alongside Somers and Korkie, a Yemeni security official told Reuters.
Lucy Somers, the photojournalist's sister, told the Associated Press that she and her father learned of her brother's death from FBI agents at 0500 GMT (12 a.m. EST) Saturday.
"We ask that all of Luke's family members be allowed to mourn in peace," she said from London.
IMMEDIATE DANGER
Kerry said the decision to mount the raid was based on fears that AQAP planned to kill Somers.
"Earlier this week, AQAP released a video announcing that Luke would be murdered within 72 hours. Along with other information, there was a compelling indication that Luke's life was in immediate danger," Kerry said.
U.S. officials on Thursday said American forces had already attempted to rescue Somers, without giving details. Yemeni officials had previously disclosed the release of six Yemenis, a Saudi and an Ethiopian hostage in a raid on Nov. 25.
There were contradictory accounts of how Saturday's raid unfolded and how many of the kidnappers were killed. A Yemeni official said on Saturday morning that 10 al Qaeda suspects had died in the raid.
A U.S. official, speaking to Reuters on condition of anonymity, said American special forces had conducted the operation alone at 1 a.m. in Yemen, but that the kidnappers had been alerted to their approach shortly before they arrived.
The official said the kidnappers then "executed" the hostages, who each sustained multiple gunshot wounds. One died during the flight out and another aboard a U.S. ship.
At no point was there an exchange of fire in the part of the compound where the hostages were being held, the source said, and at no point did U.S. forces shoot into that part of the building.
A senior U.S. official said Yemen's President Abd Rabbu Mansour Hadi had given his support for the operation.
Although the United States knew there were two hostages at the location, and that one of them was Somers, it did not know that the other was Korkie, the senior Washington official said.
The rescue team was made up of about 40 members of Special Operations forces, and the raid lasted about 30 minutes from start to finish, said the U.S. officials.
Yemen's government said in a statement carried on state media that its security forces had led the raid. It said the security forces had surrounded the house and called on the kidnappers to surrender, but they instead shot the hostages.
That led to an assault on the building in which four Yemeni security officers were also wounded, it said. The statement said the house belonged to suspected militant Saeed al-Daghaari, which another Yemeni security source told Reuters it was in the village of Dafaar in the Wadi Abadan district of Shabwa.
"It's a very small village with only 20-40 houses. There were very quick clashes with the gunmen and then it was all finished," a tribal source from the area said.
AQAP on Thursday released a video showing a man it said was Somers saying: "I'm looking for any help that can get me out of this situation. I'm certain that my life is in danger". Reuters was not able to independently verify the authenticity of that video, which was reported on by SITE Monitoring.
