The Environmental Protection Agency withdrew the air permit that was issued last summer for the proposed 1,500 megawatt Desert Rock power plant.
Sithe Global Power, LLC had planned to build the plant in northwestern New Mexico and send its power to rapidly-growing cities in Arizona and Nevada.
The regulators found the permit was issued before complete analysis of its emissions and impact on endangered species.
The move was another example of President Barack Obama's administration cracking down on coal. Interior Secretary Ken Salazar said his agency will try to overturn a Bush administration rule that made it easier for coal mining companies to dump debris from mountain-top coal mining into valley streams.
Some Navajos supported building the plant for jobs it would provide and revenue. The $3 billion to $4 billion project had been expected to bring the Navajo Nation about $50 million a year.
"Every day this project is delayed, we are losing our Navajo children to poverty and alcoholism because of lack of opportunity," Navajo President Joe Shirley said in a release.
Many other Navajos and environmentalists complained that the plant would pollute the air in a place where two large coal plants already operate and that some on the reservation would continue to go without power as the electricity was sent to the neighboring states.
Sithe Global has been trying to build the plant for years but has been stalled by the permits.
It had not yet decided whether it would bury emissions of carbon dioxide, the main greenhouse gas.