Niedringhaus, 48, who had covered conflict zones from the Balkans in the 1990s to Iraq, Libya and Afghanistan and was part of a team of AP photographers who won the Pulitzer Prize in 2005, died instantly of her wounds.
Gannon, who for many years was the news organization's Afghanistan bureau chief and currently is a special correspondent for the region, was shot three times in the wrists and shoulder. After surgery, she was in stable condition and spoke to medical personnel before being flown to Kabul.
"Anja was a vibrant, dynamic journalist well-loved for her insightful photographs, her warm heart and joy for life. We are heartbroken at her loss," said AP Executive Editor Kathleen Carroll, speaking in New York.
Niedringhaus and Gannon worked together repeatedly in Afghanistan since the 2001 U.S.-led invasion, covering the conflict from some of the most dangerous hotspots of the Taliban insurgency. They often focused on the war's impact on Afghan civilians - and they embedded several times with Afghan police and military, reporting on their determination to build up their often underequipped forces to face the fight with militants. Gannon also knows several leading Taliban well, and was one of the few Western reporters allowed into Afghanistan during the Taliban's rule in the 1990s.
Friday's attack was particularly startling because it came as an insider shooting by a member of the Afghan security forces - the first known instance of an insider attack on journalists.
It came on the eve of Afghanistan's elections for a new president and provincial councils. The Taliban have vowed to disrupt the voting and have stepped up violence in recent weeks, including increased attacks on civilian targets in Kabul and the killings of a Swedish journalist and Afghan journalist for the French news agency Agence France-Presse.
Niedringhaus and Gannon were traveling Friday in a convoy of election workers delivering ballots in the eastern city of Khost. The convoy was protected by Afghan security forces. They were in their own car with a translator and an AP Television News freelancer.
They had arrived in the heavily guarded district compound and were waiting for the convoy to move, said the freelancer, who witnessed the shooting.
A unit commander identified by authorities as Naqibullah walked up to the car, yelled "Allahu Akbar" - God is Great - and opened fire on them in the back seat with his AK-47, the freelancer said. The officer then surrendered to the other police and was arrested.
There have been repeated instances in recent years of Afghan police or military personnel opening fire on and killing international troops working with the country's security forces. The attackers are usually either suspected Taliban infiltrators or Afghans who have come to oppose the foreign presence in the country.
At their worst, in 2012, such attacks happened on average nearly once a week, killing more than 60 coalition troops and prompting NATO to reduce joint operations with Afghan forces.
Taliban spokesman Zabihullah Mujahid denied responsibility for the attack.
Khost Provincial Police Chief Faizullah Ghyrat said the attacker, Naqibullah, confessed to the shooting and told authorities he was from Parwan province, northwest of Kabul, and was acting to avenge the deaths of family members in a NATO bombing there. The claim could not be corroborated and officials said they were still investigating the shooter's background.
Ghyrat said the police commander, who he said was 25 years old, had seen the journalists, decided to act, and then demanded the assault rifle from one of his subordinates.
In a memo to AP staff, AP President Gary Pruitt remembered Niedringhaus as "spirited, intrepid and fearless, with a raucous laugh that we will always remember."
"Anja is the 32nd AP staffer to give their life in pursuit of the news since AP was founded in 1846," he wrote. "This is a profession of the brave and the passionate, those committed to the mission of bringing to the world information that is fair, accurate and important. Anja Niedringhaus met that definition in every way."
Afghan President Hamid Karzai expressed his deep sadness over Niedringhaus' death and the wounding of Gannon.
"These two AP journalists had gone to Khost province to prepare reports about the presidential and provincial council elections," a statement from Karzai's office quoted him as saying. It added that Karzai instructed the interior minister and the Khost governor to assist the AP in every way possible.
Niedringhaus was part of an AP team that won the 2005 Pulitzer Prize in breaking news photography for coverage of the war in Iraq, and was awarded the Courage in Journalism Award from the International Women's Media Foundation. She joined the AP in 2002 and had since been based in Geneva, Switzerland. From 2006 to 2007, she was awarded a Nieman Fellowship in journalism at Harvard University.
Niedringhaus started her career as a freelance photographer for a local newspaper in her hometown in Hoexter, Germany at the age of 16. She worked for the European Press Photo Agency before joining the AP. She had published two books.
Gannon, 60, is a Canadian journalist based in Islamabad who has covered Afghanistan and Pakistan for the AP since mid-1980s. One of her predecessors as Islamabad chief of bureau, Sharon Herbaugh, died in a 1993 helicopter crash in the central mountains of Afghanistan. The 39-year-old Herbaugh was the first AP newswoman and bureau chief to die on assignment.
Gannon is a former Edward R. Murrow Fellow at the Council on Foreign Relations in New York and the author of a book on the country, "I Is for Infidel: From Holy War to Holy Terror: 18 Years Inside Afghanistan."
After Friday's attack, Gannon underwent surgery in Khost. The operation was described as successful and Gannon's condition was said to be stable. She was then flown to Kabul for further treatment.
Niedringhaus drew praise from battlefields to the White House. She was honored at a United Nations briefing Friday, and in Germany, Chancellor Angela Merkel's spokesman, Steffen Seibert, tweeted condolences. White House spokesman Josh Earnest said she and Gannon were in President Obama's thoughts and prayers.
In Washington, Pentagon spokesman Col. Steve Warren condemned "this senseless act of violence against these brave professionals covering this important political transition in Afghanistan."
The Committee to Protect Journalists said the loss of Niedringhaus and the wounding of Gannon "reflect the heightened dangers of reporting from Afghanistan."
"As pre-election violence mounts, Afghanistan has become a dangerous assignment on par with the height of the Iraq war or the current situation in Syria," said Bob Dietz, CPJ's Asia program coordinator.
Afghan security and electoral officials have vowed not to let the Taliban and other militant derail the elections while conceding it is impossible to prevent the Islamic militants from waging acts of violence.
The militants have also increasingly been targeting Westerners.
The 51-year old Swedish reporter, Nils Horner, had worked for Swedish Radio since 2001 as a foreign correspondent. He was killed by a shot in the head as he was reporting on Afghanistan's election on a street in Kabul in early March. An extremist Taliban splinter group later claimed responsibility for his death.
And on March 21, four gunmen walked into the Serena Hotel in Kabul, proceeded to the hotel restaurant, pulled out pistols hidden in their shoes and killed nine people.
Among the dead was Sardar Ahmad, a widely respected 40-year-old Afghan journalist with AFP. His wife and two of their children also were killed, while their 1-year-old son was badly wounded.