Prime Minister Nuri al-Maliki said al Qaeda's Iraq leader, Abu Ayyub al-Masri, and Abu Omar al-Baghdadi, the purported head of its local affiliate, the Islamic State of Iraq, were found dead in a hole in the ground inside a house after it was surrounded and stormed by troops.
The deaths could be a major set-back to the stubborn insurgency at a time when Iraq is emerging from the sectarian slaughter unleashed after the 2003 U.S.-led invasion but still struggling to end suicide bombings and other attacks.
"The death of these two terrorists is a potentially devastating blow to al-Qaeda in Iraq," the U.S. military in Iraq said in a statement.
The killings may boost Maliki's stature as he tries to ensure his reappointment as prime minister following a March 7 general election that produced no outright winner.
Maliki's ambitions for a second term are proving to be a stumbling block to the formation of an alliance between Iraq's two main Shi'ite Muslim political groups that would give them the clout to form a coalition government.
Maliki said Masri, also known as Abu Hamza al-Muhajir and thought to be an Egyptian, and Baghdadi were killed in Thar-Thar, a rural area 80 km (50 miles) northwest of Baghdad that is regarded as a hotbed of al Qaeda activity.
The U.S. military said the operation took place on Sunday 10 km (six miles) southwest of Tikrit, Saddam Hussein's home town.
"The attack was carried out by ground forces, which surrounded the house, and also through the use of missiles," Maliki told a news conference. "U.S. forces also participated."
A U.S. soldier died in a helicopter crash during the assault, the U.S. military said. It had previously said the crash was an accident and not due to hostile fire.
An assistant of Masri's and a son of Baghdadi's were also killed in the fighting and at least 16 people were arrested.
Maliki said the house was destroyed and the bodies of Masri and Baghdadi were found in a hole in the ground inside in which they had been hiding.