Recently, Frontier Airlines and AirTran Airways announced a strategic partnership wherein Frontier EarlyReturns and AirTran A+ Rewards members can earn and redeem mileage credits on both airlines.

This unique partnership between low-cost carriers also offers travelers linked online and phone reservations systems. Both airlines will offer an integrated route map and a full list of destination options on their Web pages, thereby doubling the destinations available to their customers.

When InsideFlyer’s research first showed that something was brewing between Frontier Airlines and AirTran, we started to think of the ins and outs, and came to the conclusion that this is a huge plus for each program. While there are a few caveats, we’re all for it and here’s our advice:

If choosing one frequent flyer program over the other, go with Frontier EarlyReturns. Frontier has miles that do not expire as long as there is some sort of activity within a two-year period. AirTran, on the other had, has credits that expire 12 months after being posted.

Frontier members who have been traveling in the airline’s one class of service, can now gain access to a two-class partner if they play their reservations right, and can upgrade to a business class seat when traveling. AirTran has one of the easiest and friendliest ways for members to move forward in the plane.

AirTran members gain tremendously with this new partnership. They already have the ability to redeem their awards for any airline they choose, not just AirTran. That “other airline” award for a domestic ticket is currently 32 credits. With Frontier as a new redemption partner, if you want to redeem your credits for somewhere in the Frontier network out West, the ticket is now only 24 credits, a savings of eight credits.

While Frontier members can redeem for a free flight on AirTran for 20,000 miles (5,000 more than redeeming on Frontier), it’s an easy price to pay for the advantage of more places to earn miles. And, the 20,000 award is a better deal than the 25,000 award with United, Frontier’s main competitor.

This partnership is being billed as the first merger/relationship of its kind for low-cost carriers. We really hate to take on the spinners for this angle, but we think Southwest and ATA beat them to it. But ask Avis, being second with these types of relationships isn’t all that bad.

What we like about the deal is that the analysts on Wall Street were all predicting that Frontier and Spirit might make good merger partners because of the compatibility of their fleets. But as we see here, alliances for second tier airlines can also be played out and with even bigger gains. Frontier may still be able to play the field for more partners, and they gain significantly with this virtual merger.

One caveat, so don’t blame us if you mess up after reading this. The only way this works is if you do indeed book your travel on the airline partner, either Frontier or AirTran, with the airlines’ Web sites. Going to Expedia, booking a ticket and then trying to get cross program credit is not going to get you anywhere. This is similar to restrictions that some hotel programs have in that you won’t earn credit when booking through a third party agent. So, be bonus miles and credits aware.

In closing, there is one more silver lining to this: all those dumpster divers who earned credits in the AirTran program by collecting used drink cups at Wendy’s will now have somewhere else to fly (we’re referring to a 2005 AirTran promotion wherein A+ Rewards members could earn flight credits when purchasing a Coca-Cola beverage at Wendy’s).

Bottom line: No one is harmed and everyone should be very happy with this reciprocal frequent flyer deal, we certainly are.