Twenty-one people were killed in the Garuda plane crash last March.
The national carrier, Garuda Indonesia, was promoted to the top safety category, three months after one of its planes crashed, killing 21 people.
The transport ministry also approved Adam Air. One of its jets vanished in January, along with 102 passengers.
Nineteen out of 21 airlines audited were allowed to continue operating.
Five Australians were among those killed in March when a Garuda plane overshot the runway and burst into flames in the Indonesian city of Yogyakarta.
The government review comes after the United States advised its citizens to avoid flying Indonesian airlines amid concerns about their safety standards.
The Indonesian audit was based on criteria such as surveillance, ramp checks, personnel, department safety, number of accidents and number of serious incidents.
Indonesia has shut down four airlines and grounded five others with the potential of similar licence revocations for failing to meet safety standards.

The largest company to lose its licence is Jatayu Gelang Sejahtera. The other companies are all small airlines operating only aircraft with a passenger capacity of fewer than thirty, and are Aviasi Upataraksa, Alfa Trans Dirgantara and Prodexim. The companies that were grounded pending either improvements or licence revokation are Germania Trisila Air, Atlas Delta Setia, Survey Udara Penas, Kura-kura Aviation and SMAC, all of which also operate only aircraft with under-30 passenger capacities. They have three months to improve, or their licences will be revoked.

Jatayu had already ceased operations in August, but had intended to restart with a 150-seat Boeing 737. The licence was revoked because the state requires at least two aircraft to be commercially operated and because of the fact that it "was lacking in pilots and human resources". Also, the age of the jetliner meant that it would require a test called a 'C-Check' before it could begin commercial services, at a cost of $120,000.

The action comes as the result of a number of air crashes, namely the Adam Air Flight 574 disaster in which 102 people were killed, and the Adam Air Flight 172 accident, in which a plane snapped in half during a hard landing, but managed to hold together, thus preventing any serious injuries. As a result, all 54 of Indonesia's airlines were given a safety rating, with a level-1 rating meaning no action was needed, a level-2 rating meaning the airline needed to make some improvements, and a level-3 rating requiring that the airline be shut down unless improvements were made within three months. Most airlines received a level-2 rating, while none received the top rating. Adam Air was among the airlines to receive the level-3 rating, but was upgraded to tier 2 at the same time as the groundings.

Meanwhile, state-owned Garuda Indonesia is now the only airline to have a type-1 rating, despite the fatal crash of Garuda Indonesia Flight 200 in March. According to the Indonesian Transport Ministry's Director General for Aviation Budi Mulyawan Suyitno, Garuda now satisfied 84 percent of civil aviation standards.

The ratings have been based on such criteria as surveillance, ramp checks, personnel, department safety, number of accidents and number of serious incidents, according to the BBC. Meanwhile, ''Flight Global'' is reporting that, according to Directorate General of Air Communications (DGAC) director of air certification office, Yurlis Hasibuan “20 criteria including whether the airline has developed better safety and human resources” are checked.