If confirmed, Lazcano's death would mark a huge victory for Mexican law enforcement, and mark the end of a founder of one of the world's bloodiest cartels.
The navy said there were "strong indications" the body of one of two men killed in the shootout Sunday was Lazcano, known as "El Lazca." But it added that more forensics tests would have to be carried out to confirm the identification.
"Information was obtained after the first forensics tests were carried out that yielded indications that suggest that one of the bodies is Heriberto Lazcano," the navy's statement said.
"The Navy Department is coordinating efforts with Coahuila state, and will be awaiting the conclusions of the forensics examination in the case," the statement said.
The death of Lazcano would be a major victory for Mexican law enforcement. The Zetas cartel that he helped found with other deserters from an elite army unit went on to carry out some of Mexico's bloodiest massacres, biggest jail breaks and fiercest attacks on authorities.
Lazcano, who is also known as "El Verdugo" (the Executioner) for his brutality, is suspected in hundreds of killings, including the June 2004 slaying of Francisco Ortiz Franco, a top editor of a crusading weekly newspaper in Tijuana that often reported on drug trafficking. Ortiz Franco was gunned down in front of his two young children as he left a clinic.
The United States has offered a $5 million reward and Mexico an additional $2.3 million for information leading to Lazcano's arrest.
The Sunday shootout came in the rural area of Progreso, Coahuila, about 80 miles (125 kilometers) west of the Texas border, near Laredo.
The navy said it received complaints about armed men in the area and sent out a patrol to check out the reports. Gunmen tossed grenades at the patrol from a moving vehicle, wounding one of the marines. His injuries were not life-threatening.
Two of the gunmen were killed in the ensuing shootout, the navy's statement said. In the gunmen's' vehicle, authorities found a grenade launcher, 12 grenades, what appeared to be rocket propelled grenade launcher and two rifles.
Under Lazcano's leadership, the Zetas recruited more hit men, many of them former Mexican soldiers, and hired "kaibiles," Guatemalan soldiers trained in counterinsurgency, transforming what had been a small group of assassins into a ruthless gang of enforcers for the Gulf cartel. The Zetas also were in charge of protecting the Gulf cartel's drug shipments.
The Zetas finally split from their former bosses in 2010 and have since been fighting a vicious battle for control of the drug business in northeastern Mexico, the traditional home base of the Gulf cartel. The result has been a surge of drug-related killings.
Lazcano "is credited with strengthening the organization ... he created a new structure of regional cells that specialize in specific crimes," Mexican federal prosecutors say in their profile of Lazcano.
The Zetas earned their notoriety for brutality by becoming the first to publicly display their beheaded rivals, most infamously two police officers in April 2006 in the resort city of Acapulco. The severed heads were found on spikes outside a government building with a message signed "Z'' that said: "So that you learn to respect."
Even with the death of Lazcano, the Zetas would still be run by a ruthless capo, Miguel Angel Trevino Morales, who has a reputation for being even more brutal than Lazcano. Trevino Morales, also known was "Z 40," has taken on a greater leadership role and has even been reported to have replaced Lazcano as operational chief.
The report of Lazcano's death came just hours after the navy nabbed a suspected Zetas regional leader accused of involvement in some of the country's most notorious crimes in recent years.
Navy spokesman Jose Luis Vergara said Salvador Alfonso Martinez Escobedo was arrested Saturday in Nuevo Laredo, across from Laredo, Texas. The official said Martinez is believed to have masterminded the massacre of 72 migrants in the northern state of Tamaulipas in 2010.
The man known as "Squirrel" also has been linked to the escape of 151 prisoners in 2010 from a jail in the city of Nuevo Laredo, the recent flight of 131 prisoners in the city of Piedras Negras and the killing of U.S. citizen David Hartley in 2010 on Falcon Lake, which straddles the U.S.-Mexico border.
The death of Hartley drew wide attention as it appeared Hartley and his wife, Tiffany, were on a personal trip when he was shot by Mexican criminals on Sept. 30, 2010. The Hartleys were using personal watercraft on Falcon Lake when David Hartley was shot in the head and fell into the water.
The navy is also blaming Martinez for the killing of the Tamaulipas state police commander and chief investigator on the case, an attack that hampered the investigation.
The navy said Martinez is also a suspect in dozens of killings of people who were buried in mass graves at the same site of the 2010 massacre of migrants. Nearly 200 bodies were discovered in April 2011 in the town of San Fernando, close to the U.S. border. Those two crimes have been the most fatalities since Mexico's federal government launched an armed offensive against drug traffickers in December 2006.
Associated Press writers Olga R. Rodriguez and E. Eduardo Castillo contributed to this report