EMPLOYMENT AGREEMENT

Exhibit 10.58

EMPLOYMENT AGREEMENT

BETWEEN

AIRTRAN HOLDINGS, INC. AND

ROBERT FORNARO

This Employment Agreement (henceforth the “Agreement”) effective as of November 1, 2007 (the “Effective Date”) by and between ROBERT FORNARO (henceforth the “Executive”) and AIRTRAN HOLDINGS, INC., a Nevada corporation (henceforth the “Company”).

RECITALS

WHEREAS, the non-management members of the Company’s Board of Directors (henceforth the “Board”) believe the Executive to be the best qualified individual to protect and enhance the best interests of the Company and its stockholders and that entering into this Agreement to ensure the Executive’s continued and long-term employment with the Company is in the best interests of the Company and its stockholders; and

WHEREAS, the Board recognizes that, as in the case of many publicly-held corporations, the possibility of a change of control may exist and that the uncertainty and questions which such possibility may raise among management may result in the departure or distraction of management personnel to the detriment of the Company and its stockholders; and

WHEREAS, the Board has determined that in the event of that contingency, it is imperative to be able to rely on management’s continuance and in particular, the leadership of the Executive and that appropriate steps should be taken to secure that essential service; and

WHEREAS, the Board and the Executive also desire to provide for a change of status for the Executive during the term of this Agreement in order to maintain the Executive’s continuing services ; and

WHEREAS, the Executive and the Company now desire to enter into this Agreement;

NOW, THEREFORE, for and in consideration of the premises and mutual covenants and promises contained herein, the Company and the Executive agree as follows:

CONTRACT TERMS

1.1 “Affiliate” means any Person directly or indirectly controlling or controlled by or under the direct or indirect common control with such Person. For purposes of this definition, “control” when used with respect to any Person means the power to direct the

management and policies of such Person, directly or indirectly, whether through the ownership of voting securities, by contract, or otherwise.

1.2 “Affiliated Company” means:

1.2.1 A member of a controlled group of corporations of which the Company is a member or;

1.2.2 An unincorporated trade or business which is under common control with the Company as determined in accordance with Section 414(c) of the Internal Revenue Code of 1986, as amended (henceforth the “Code”) and regulations issued thereunder.

1.2.3 For purposes hereof, a “controlled group of corporations” shall mean a controlled group of corporations as defined in Section 1563(a) of the Code determined without regard to Section 1563(a)(4) and (e)(3)(C) of the Code.

1.3 A “Change of Control” will be deemed to have occurred in the event that, after the Effective Date, any of the following events shall have occurred:

1.3.1 Any Person, or Persons acting together that would constitute a “group” (a “Group”), for purposes of Section 13(d) of the Securities Exchange Act of 1934 as from time to time amended, together with any Affiliates or Related Persons thereof (other than any employee stock ownership plan), beneficially owns 20% or more of the total voting power of all classes of Voting Stock of the Company;

1.3.2 Any Person or Group, together with any Affiliates or Related Persons thereof, succeeds in having a sufficient number of its nominees elected to the Board of Directors of the Company such that such nominees, when added to any existing director remaining on the Board of Directors of the Company after such election who is an Affiliate or Related Person of such Person or Group, will constitute a majority of the Board of the Company;

1.3.3 There occurs any transaction, or series of related transactions, and the beneficial owners of the Voting Stock of the Company immediately prior to such transaction (or series) do not, immediately after such transaction (or series) beneficially own Voting Stock representing more than 50% of the voting power of all classes of Voting Stock of the Company (or in the case of a transaction (or series) in which another entity becomes a successor to the Company, of the successor entity); or,

1.3.4 The Company shall cease to own a majority of the capital stock of its operating subsidiaries;

1.4 “Disability” shall mean the permanent and total inability by reason of mental or physical infirmity or both, of the Executive to perform the work customarily assigned to him. Additionally, a medical doctor, selected or approved by the Board must advise the Board that it is either not possible to determine when such Disability will

2

terminate or that it appears probable that such Disability will be permanent during the remainder of the Executive’s lifetime. If the Company secures an “own occupation” disability policy to cover its liability pursuant to this Agreement, such definition in the policy shall be deemed to control.

1.5 “Notice of Termination” means a notice which shall indicate the specific Termination provision in this Agreement relied upon and shall set forth in reasonable detail the facts and circumstances claimed to provide a basis for Termination of Executive’s employment under the provision so indicated.

1.6 “Normal Retirement Date” means a date selected on written notice to the Company by the Executive on which the Executive shall retire from, and cease to perform services for, the Company in accordance with Company policy. The Executive’s retirement from, and cessation of performing services for, the Company upon his reaching such Normal Retirement Date shall constitute a Termination but shall not entitle Executive to benefits under Section 15 or Section 16 of this Agreement.

1.7 “Person” means any individual, corporation, partnership, trust, joint venture or other legal entity holding, or acquiring Voting Stock of the Company.

1.8 “Related Person” means, with respect to any Person, any other Person owning:

1.8.1    5% or more of the outstanding Common Stock of such Person; or,

1.8.2    5% or more of the Voting Stock of such Person.

1.9 “Termination” shall mean a cessation of the employment relationship between the Executive and the Company that constitutes a “separation from service” within the meaning of Code Section 409A, and the terms “Terminate” and “Terminated” shall have correlative meanings.

1.10 “Termination for Cause” means the Termination as a result of a conviction for a willful violation of any law, rule or regulation (other than traffic violations or similar offenses), or a material breach of this Agreement on the part of the Executive that is not cured within ten (10) business days of notification by the Company.

1.11 “Voting Stock” means any equity security or series of equity securities, issued by the Company which are entitled to vote for Directors of the Company.

2.1 Term—The term of this Agreement shall commence on the date first noted above, and shall terminate on the third anniversary of such date (“Term”) unless extended, pursuant to Section 2.2, or modified pursuant to Section 3.2.

2.2 Extension—This Agreement shall be automatically extended by one year upon the expiration of the Term or any renewal term, unless the Company provides 90

3

days notice before such expiration of the intention to terminate the Agreement (“Extended Term”). No termination of this Agreement pursuant to the Company’s providing such notice shall constitute Termination of Executive’s employment by the Company for purposes of determining whether, or to what extent, a benefit is payable hereunder.

3.1 Executive shall be employed by Company as its President and Chief Executive Officer during the Term of this Agreement except as provided in Section 3.2 below. Executive shall report directly and solely to Company’s Board of Directors. The Board agrees to nominate Executive for election to the Board as a member of its slate at each annual meeting of stockholders during the Term. Executive agrees to serve on the Board if elected. The duties and responsibilities of President and, Chief Executive Officer shall be as defined in the By-Laws of Company in effect as of the date hereof, and shall be without consideration of other positions Executive may hold with the Company. Executive’s services are mutually agreed to be unique.

3.2 During Executive’s period of service hereunder, Executive agrees to perform such services not inconsistent with his position as shall from time to time be assigned to him by the Company’s Board. During the Term, except for Disability, illness and vacation period and except as otherwise provided herein, Executive shall devote his full productive time, attention and energies to the position of President and Chief Executive Officer.

3.3 Executive’s expenditure of reasonable amounts of time in connection with outside activities, not competitive with the business of the Company, such as outside directorships or charitable or professional activities shall not be considered in contravention of this Agreement so long as such activities do not materially interfere with his performance of this Agreement. Further, it is understood and agreed by the parties hereto that Executive is entitled to engage in passive and personal investment activities not materially interfering with his performance of this Agreement.

3.4 Service as an executive of an Affiliated Company, whether separately compensated or not, shall not be considered in contravention of this Agreement.

4.1 Throughout the Term of this Agreement, the Executive shall receive an annual base salary of at least $ 500,000.

4.2 The Compensation Committee of the Board shall review the Executive’s salary at least annually, at or during the July Compensation Committee meeting. The Compensation Committee may increase the base salary based upon relevant considerations, including, but not limited to the performance of the Executive and the Company, changes in the cost of living and competitive compensation data.

4

In addition to the salary stated in Section 4, the Executive shall be eligible during the Term for an annual cash incentive award based on his performance and the performance of the Company in accordance with the management incentive plan as it may be in effect from time-to-time with an annual target of one hundred and fifty percent (150%) of the Executive’s year-end base salary rate. Any such cash incentive award shall be paid to Executive not later than 2  ¹ / 2 months following the close of the calendar year to which such incentive award relates.

6.1 As of the Effective Date, the Executive shall be granted an aggregate of 300,000 shares of the Company’s Common Stock, par value $.001 per share (“Shares”).

6.1.1 The Shares shall vest as follows: 33  ¹ / 3 % on November 1, 2008, 33  ¹ / 3 % on November 1, 2009 and 33  ¹ / 3 % on November 1, 2010.

6.1.2 All Shares granted prior to the date of Termination of Executive’s employment without Cause shall vest 100% if the Executive is Terminated without Cause (including Termination due to death or Disability).

6.1.3 All Shares granted before a Change of Control shall accelerate and become fully vested in the event of a Change of Control.

6.2 In addition to the one-time grant provided in section 6.1 above, Executive shall be eligible for annual stock grants at times and in amounts to be determined by the Board. Annual stock grants: (a) may be awarded in restricted stock or in any such other form as is permitted under the Company’s 2002 Long Term Incentive Plan; (b) will have a target value equivalent to 75,000 shares of the Company’s Common Stock but at the Board’s discretion have a larger or lesser value based on the circumstances at the time the grant; and (c) be awarded based upon the achievement of pre-determined performance objectives established by the Board of Directors.

6.3 The Executive, in accordance with the Company’s standard policies shall have the right to exercise any Stock Options previously granted under either the 1996 Stock Option Plan and/or the 2002 Long Term Incentive Plan at a date which is not later than the expiration of the later of one (1) year after the Executive’s Normal Retirement Date or the end of the Term of this Agreement, but in no event later than the expiration date of the option; provided that no Stock Option granted or vesting after December 31, 2004, shall be exercisable after the last date permitted for exercise pursuant to the terms of the applicable Stock Option.

5

The Executive, during the Term shall be authorized to incur and shall be reimbursed by the Company for all reasonable expenses for the advancement of the Company’s business pursuant to standing Company policy at least monthly. The Executive agrees to provide to the Company such information as may be reasonably necessary to substantiate any reimbursement or payment of such expenses at such time as is consistent with Company policy but in no event later than 30 days following the close of the calendar year in which such expense is incurred. Upon receipt of such substantiation, the Company shall pay or reimburse such expenses promptly in accordance with Company policy but in no event later than 2  ¹ / 2 months following the close of the calendar year in which such expense was incurred by the Executive.

The Executive and/or his spouse, on or after the Executive’s Normal Retirement Date and/or immediately upon Termination under Sections 10, 12, 13.3, 13.4 and/or 15 hereunder, shall be entitled to participate in such postretirement medical/dental plans that the Company makes available to other retired officers; provided, however, that:

8.1 In the event of a Termination for Cause under Section 12.2, the entitlement of the Executive and/or his spouse to participate in such postretirement medical/dental plans shall end on the third anniversary of such Termination; and

9.1 The Executive shall be eligible to participate in any and all other benefit programs which are, and which may be in the future, generally available to members of the Company’s management, including, but not limited to group health, disability, and life insurance benefits, participation in any pension, retirement and/or profit-sharing plans, financial planning, or other perquisites.

9.2 Except as otherwise provided herein, the Company shall provide free on-line air transportation on any route maintained by the Company for the Executive and his spouse for the lifetimes of both the Executive and his spouse. The Company shall provide to the Executive’s pass-eligible dependents free on-line air transportation as and to the extent provided in the Company’s pass policy.

9.3 During the Term, the Company shall reimburse the Executive for all medical and dental expenses incurred by the Employee and his spouse. Expenses for medical care shall be deemed to include all amounts paid with respect to hospital bills, doctor and dental bills and drugs which are not compensated by insurance policies maintained by the Company. The Executive agrees to provide to the Company such information as may be reasonably necessary to substantiate any reimbursement or payment of such expenses not later than 30 days following the close of the calendar year in which such expense is incurred. Upon receipt of such substantiation, the Company shall promptly pay or reimburse such expenses, but in no event later than 2  ¹ / 2 months following the close of the calendar year in which such expense was incurred by the Executive or his spouse.

6

If the Executive’s services hereunder are Terminated due to Disability as defined in the Agreement, the Executive shall receive:

10.1 His full salary for the remainder of the Term, payable in accordance with the regular payroll practices of the Company, offset by any amounts payable from a disability policy maintained by the Company.

10.2 Any stock options, stock grants or stock appre