FIRST SUPPLEMENTAL INDENTURE

Exhibit 4.1

FIRST SUPPLEMENTAL INDENTURE

By and Among

ExpressJet Holdings, Inc.

as Issuer,

ExpressJet Airlines, Inc.,

as Guarantor,

and

The Bank of New York Mellon Trust Company, N.A.,

as Trustee

Dated as of

July 30, 2008

A SUPPLEMENTAL INDENTURE

REGARDING

4.25% Convertible Notes due 2023

FIRST SUPPLEMENTAL INDENTURE

FIRST SUPPLEMENTAL INDENTURE dated as of July 30, 2008, among ExpressJet Holdings, Inc., a Delaware corporation (the “Company”), ExpressJet Airlines, Inc., a Delaware corporation (the “Guarantor”), and The Bank of New York Mellon Trust Company, N.A. (as successor in interest to Bank One, N.A.), as trustee (the “Trustee”);

WHEREAS, the Company and the Guarantor have heretofore executed and delivered to Bank One, N.A., as predecessor in interest to the Trustee, an indenture, dated as of August 4, 2003 (the “Indenture”), to provide for the issuance of the Company’s 4.25% Convertible Notes due 2023 (the “Securities”); and

WHEREAS, Section 9.01 of the Indenture provides, among other things, that the Company and the Trustee may amend the Indenture or the Securities without the consent of any Securityholder (as defined in the Indenture) to add to the Company’s or the Guarantor’s covenants for the benefit of the Securityholders, to add any additional Events of Defaults (as defined in the Indenture) or to provide security for the Securities; and

WHEREAS, the Company desires to amend the Indenture and the Securities as permitted by Section 9.01; and

WHEREAS, all action on the part of the Company necessary to authorize its execution, delivery and performance of the Indenture, as supplemented by this First Supplemental Indenture, has been duly taken; and

WHEREAS, the Company desires and has requested the Guarantor and the Trustee to join in the execution and delivery of this First Supplemental Indenture for the purpose of amending the Indenture and the Securities;

NOW THEREFORE, in consideration of the premises and for other good and valuable consideration, it is mutually covenanted and agreed for the equal and ratable benefit of all Securityholders as follows:

ARTICLE ONE

DEFINITIONS, ETC.

Section 1.1 Definitions. Each capitalized term that is used herein and is defined in the Indenture shall have the meaning specified in the Indenture unless such term is otherwise defined herein, in which case such term shall have the meaning specified herein.

Section 1.2 Conflict with Indenture. To the extent that any of the terms set forth in this First Supplemental Indenture shall conflict with any of the terms of the Indenture or the Securities, the terms of this First Supplemental Indenture shall be controlling.

ARTICLE TWO

AMENDMENTS TO INDENTURE

Section 2.1 Additional Covenants. Article IV of the Indenture is hereby amended by adding the following new Sections 4.08 and 4.09 to read as follows:

“SECTION 4.08. Payment of Additional Interest. Effective from and after the Effective Time, and notwithstanding anything to the contrary in this Indenture, in any Security or in the form of the Notes as set forth on Exhibit A-1, the Company promises to pay additional interest on the Principal Amount of the Securities at a rate of 7.00% per year from the Effective Time. During such period, the Company will pay such additional interest semiannually in arrears on each Interest Payment Date, commencing on February 1, 2009, and otherwise in accordance with the provisions of the Indenture and the Securities relating to the payment of interest. Without limiting the generality of the foregoing, such additional interest shall constitute “interest” for purposes of Section 6.01(1) of the Indenture.

SECTION 4.09. Additional Repurchase Date. Effective from and after the Effective Time, the date August 1, 2011 shall also be a “Repurchase Date” in addition to the dates set forth in Section 3.08.”

Section 2.2 Conforming Amendments Regarding Additional Covenants.

“, and additional interest on the Principal Amount of the Securities at a rate per annum of 7.00% per year from the Effective Time.”

Section 2.3 Title Change. The series of Securities previously designated as the “4.25% Convertible Notes due 2023” shall be designated as the “11.25% Convertible Secured Notes due 2023.”

Section 2.4 Additional Article. The Indenture is hereby amended by adding an additional new Article to be designated “ARTICLE XIV COLLATERAL AND SECURITY” and to read as follows:

2

“ARTICLE XIV

COLLATERAL AND SECURITY”

SECTION 14.01. Security.

(a) From and after the Effective Time, the payment of the Securities, when due, and the performance of all other obligations of the Company and Guarantor under the Securities, this Indenture the Guarantee, and the Security Documents are secured by Liens upon the Guarantor’s rights in the Collateral.

(b) The Company shall, and shall cause the Guarantor to, do or cause to be done, at the sole expense of the Company and/or the Guarantor, all acts and things which may be required, or that the Collateral Agent from time to time may reasonably request, to assure and confirm that the Collateral Agent holds, for the benefit of the Holders of Securities, duly created, enforceable and perfected Liens upon the Collateral as contemplated by this Indenture and the Security Documents, so as to render the same available for the security and benefit of this Indenture and of the Securities and the Guarantee, according to the intent and purposes hereof expressed, subject in each case to any express provisions of any Security Documents. The Company shall take, or shall cause the Guarantor to take, upon request of the Trustee or Collateral Agent, any an all actions reasonably to create and maintain, as security for the obligations of the Company and Guarantor under this Indenture, the Guarantee and the Security Documents, a valid and enforceable perfected first priority Lien (subject to Permitted Liens) in and on the Collateral, in favor of the Collateral Agent and the Trustee, as the case may be, for the benefit of the Securityholders, which Lien is superior to and prior to the rights of all third Persons and subject to no other Liens, except Permitted Liens.

SECTION 14.02. Collateral Agent and Security Agreement.

(a) The Company and the Guarantor will enter into the Security Agreement with the Collateral Agent which sets forth the terms on which the Collateral Agent receives, holds, administers, maintains, enforces and distributes the proceeds of all Liens upon any Collateral at any time delivered to it, in trust for the benefit of the present and future Holders of the Securities.

(b) The Collateral Agent is authorized and empowered to appoint one or more co-Collateral Agents as it deems necessary or appropriate. Neither the Collateral Agent nor the Trustee shall not be responsible for any misconduct or negligence of any such co-Collateral Agent appointed with due care.

(c) Neither the Trustee nor the Collateral Agent nor any of their respective officers, directors, employees, attorneys or agents shall be responsible or liable for the existence, genuineness, value or protection of any Collateral, for the legality, enforceability, effectiveness or sufficiency of the Security Documents, for the creation, perfection, priority, sufficiency or protection of any Lien, or for any defect or deficiency as to any such matters, or for any failure to demand, collect, foreclose or realize upon or otherwise enforce any of the Liens or Security Documents or any delay in doing so.

(d) The Company appoints The Bank of New York Mellon as the initial Collateral Agent. The duties, rights, powers, and immunities of the Collateral Agent are

3

contained in the Security Agreement to which reference is hereby made. No implied The Collateral Agent undertakes to perform such duties, and only such duties as are expressly herein and in the Security Agreement, and no implied covenants or obligations shall be read into this Indenture or the Security Agreement against the Collateral Agent.

SECTION 14.03. Release of Security Interests.

(a) In accordance with the provisions of the Security Agreement or as provided hereby, the Collateral Agent’s Liens upon the Collateral will be released:

(1) Upon the Discharge Date;

(2) as to any or all Collateral at any time, if (A) written consent to the release of Collateral has been given by an Act of Required Holders and (B) such release has become effective in accordance with the terms of such consent; or

(3) in accordance with the provisions of Section 14.05 and the Security Documents as in effect at the time of such release.

(b) The Collateral Agent’s Liens upon Collateral will no longer secure the Securities and the right of the Holders to the benefits and proceeds of the Collateral Agent’s Liens on Collateral will terminate and be discharged:

(1) upon discharge of this Indenture as set forth under in Section 8.01 hereof; or

(2) upon payment of the Securities, in full in cash or Common Stock, and the payment and satisfaction of all other related obligations of the Company and the Guarantor under the Securities, this Indenture and the Security Documents that are outstanding, due and payable at the time the Securities are so paid in full.

(c) The Company will otherwise comply with the provisions of TIA §314(b). To the extent applicable, the Company will cause TIA §313(b), relating to reports, and TIA §314(d), relating to the release of property or securities or relating to the substitution therefor of any property or securities to be subjected to the Liens imposed hereby and by the Security Documents, to be complied with. Any certificate or opinion required by TIA §314(d) may be an Officer’s Certificate, except in cases where TIA §314(d) requires that such certificate or opinion be made by an independent Person, which Person will be an independent appraiser or other expert selected or approved by the Trustee with reasonable care. To the extent applicable, the Company will furnish to the Trustee, prior to each proposed release of Collateral pursuant to the terms hereof and the Security Documents (i) all documents required by TIA §314(d); and (ii) an Opinion of Counsel to the effect that such accompanying documents constitute all documents required by TIA §314(d).

SECTION 14.04. Recording and Opinions.

(a) The Company shall furnish to the Collateral Agent and the Trustee contemporaneously with the execution and delivery of this First Supplemental Indenture and

4

promptly after the execution and delivery of any other instrument of further assurance or amendment, an Opinion of Counsel (i) stating that in the opinion of such counsel the Security Documents are effective to create a Lien in the Collateral to the extent that the Guarantor has rights in or the power to transfer such Collateral and creation of a Lien in such collateral is governed by Article 9 of the UCC; and (ii) stating that in the opinion of such counsel, all action has been taken with respect to the filing of financing statements as is necessary to perfect the Lien in that portion of the Collateral (x) in which the Company has rights or the power to transfer, (y) the creation and perfection of a Lien which is governed by Article 9 of the UCC and (z) in which a Lien can be perfected by filing a financing statement under the UCC. Such Opinion of Counsel shall also address matters pertaining to the recordation of the Collateral with the Federal Aviation Aircraft Registry and the registration of the Liens in the International Registry as the Trustee may reasonably request.

(b) The Company shall furnish to the Collateral Agent and the Trustee on February 1 of each year beginning with February 1, 2008, an Opinion of Counsel, as of such date, stating that all action has been taken with respect to the filing of financing statements, continuation statements and other registrations and recordings as is necessary for the Lien in that portion of the collateral subject to the Security Documents (x) in which the Company has rights or the power to transfer, (y) the creation and perfection of a Lien which is governed by Article 9 of the UCC, and (z) in which a Lien can be perfected by filing a financing statement under the UCC, to continue to be perfected (or stating, in the opinion of such counsel. that no such action is necessary to maintain the Liens created by the Security Documents and the perfection thereof). Such Opinion of Counsel shall also address matters pertaining to the recordation of the Collateral with the Federal Aviation Aircraft Registry and the registration of the Liens in the International Registry as the Trustee may reasonably request.

(c) The Company will otherwise comply with the provisions of TIA §314(b).

SECTION 14.05. Release of Collateral.

(a) Subject to subsections (b), (c) and (d) of this Section 14.05, Collateral may be released from the Liens and security interest created by the Security Documents at any time or from time to time in accordance with the provisions of the Security Documents or as provided hereby. In addition, upon the request of the Company pursuant to an Officers’ Certificate certifying that all conditions precedent hereunder have been met, then (at the sole cost and expense of the Company) the Collateral Agent will, without any representation or warranty, release Collateral that is sold, conveyed or disposed of in compliance with the provisions of the Security Documents. Upon receipt of such Officers’ Certificate, the Collateral Agent shall, at the sole cost and expense of the Company and without any representation or warranty, execute, deliver or acknowledge any necessary or proper instruments of termination, satisfaction or release to evidence the release of any Collateral permitted to be released pursuant to this Indenture or the Security Documents.

(b) No Collateral may be released from the Liens created by the Security Documents pursuant to the provisions of the Security Documents unless the Officer’s Certificate required by this Section 14.05, together with any Officer’s Certificate required by such Security Documents, have been delivered to the Collateral Agent.

5

(c) At any time when a Default or Event of Default has occurred and is continuing and the maturity of the Securities has been accelerated (whether by declaration or otherwise) and the Trustee has delivered a notice of acceleration to the Collateral Agent, no release of Collateral pursuant to the provisions of the Security Documents will be effective as against the Holders of Securities.

(d) The release of any Collateral from the terms of this Indenture and the Security Documents will not be deemed to impair the security under this Indenture in contravention of the provisions hereof if and to the extent the Collateral is released pursuant to the terms hereof and of the Security Documents. To the extent applicable, the Company will cause TIA § 313(b), relating to reports, and TIA § 314(d), relating to the release of property or securities from the Liens and security interest imposed by the Security Documents and relating to the substitution therefor of any property or securities to be subjected to the Lien and security interest of the Security Documents, to be complied with. Any certificate or opinion required by TIA § 314(d) may be made by an Officer in an Officer’s Certificate, except in cases where TIA § 314(d) requires that such certificate or opinion be made by an independent Person, which Person will be an independent appraiser or other expert selected or approved by the Trustee with reasonable care.

SECTION 14.06. Certificates of the Company. The Company will furnish to the Trustee and the Collateral Agent, prior to each proposed release of Collateral pursuant to the Security Documents (i) all documents required by TIA §314(d); and (ii) an Opinion of Counsel, which may be rendered by internal counsel to the Company, to the effect that such accompanying documents constitute all documents required by TIA §314(d). The Trustee may, to the extent permitted by Sections 7.01 and 7.02 hereof, accept as conclusive evidence of compliance with the foregoing provisions the appropriate statements contained in such documents and such Opinion of Counsel.

SECTION 14.07. Certificates of the Trustee. In the event that the Company wishes to release Collateral in accordance with the Security Documents and has delivered the certificates and documents required by the Security Documents and Sections 14.05 and 14.06 hereof, the Trustee will determine whether it has received all documentation required by TIA § 314(d) in connection with such release and, based on such determination and the Opinion of Counsel delivered pursuant to Section 14.06(ii) hereof, will deliver a certificate to the Collateral Agent setting forth such determination.

SECTION 14.08. Authorization of Actions to Be Taken by the Trustee Under the Security Documents. Subject to the provisions of Section 7.01 and 7.02 hereof, the Trustee may, in its sole discretion and without the consent of the Holders of Securities, direct, on behalf of the Holders, the Collateral Agent to, take all actions it deems necessary or appropriate in order to (i) enforce any of the terms of the Security Documents; and (ii) collect and receive any and all amounts payable in respect of the obligations of the Company hereunder. The Trustee will have power to institute and maintain such suits and proceedings as it may deem expedient to prevent any impairment of the Collateral by any acts that may be unlawful or in violation of the Security Documents or this Indenture, and such suits and proceedings as the Trustee may deem expedient to preserve or protect its interests and the interests of the Holders of Securities in the Collateral (including power to institute and maintain suits or proceedings to restrain the enforcement of or

6

compliance with any legislative or other governmental enactment, rule or order that may be unconstitutional or otherwise invalid if the enforcement of, or compliance with, such enactment, rule or order would impair the security interest hereunder or be prejudicial to the interests of the Holders or of the Trustee).

SECTION 14.09. Authorization of Receipt of Funds by the Trustee Under the Security Documents. The Trustee is authorized to receive any funds for the benefit of the Holders of Securities distributed under the Security Documents, and to make further distributions of such funds to the Holders according to the provisions of this Indenture.

SECTION 14.10. Termination of Security Interest. Upon discharge of this Indenture as set forth under in Section 8.01 hereof, the Trustee will, at the request of the Company, deliver a certificate to the Collateral Agent stating that such obligations have been paid in full, and instruct the Collateral Agent to release the Liens pursuant to this Indenture and the Security Documents (subject to the satisfaction of any release of Lien provisions set forth in the Security Documents).

SECTION 14.11. Additional Rights of Trustee. In addition to the rights of Trustee set forth in Section 7.02, subject to its duties and responsibilities under the provisions of Section 7.01, and, except as expressly excluded from this Indenture pursuant to said Section 7.01, subject also to its duties and responsibilities under the TIA:

The rights, privileges, protections, immunities and benefits given to the Trustee, including, without limitation, its right to be indemnified, are extended to, and shall be enforceable by, the Trustee in each of its capacities hereunder or under the Security Documents (including as Collateral Agent under the Security Documents), and each agent, custodian and other Person (including any co-Collateral Agent or separate collateral agent under the Security Document) employed to act hereunder or under the Security Documents.

SECTION 14.12. Amendment of Security Documents. The Security Agreement provides that no amendment or supplement to the provisions of any Security Document will be effective without the approval of the obligors party thereto and the Collateral Agent acting as directed by an Act of Required Holders, except that:

7

Any amendment or supplement to the provisions of the Security Documents that releases Collateral will be effective only in accordance with the requirements set forth in Section 14.03, 14.05 and 11.03 hereof.

SECTION 14.13. Additional Definitions. In addition to the definitions set forth in Article I, the following definitions shall also apply under this Indenture:

“Act of Required Holders” means, as to any matter at any time prior to the discharge of the Indenture, a direction in writing delivered to the Collateral Agent by or with the written consent of the Holders of more than 50% of the aggregate outstanding Principal Amount of Securities. For purposes of this definition, (a) Securities registered in the name of, or beneficially owned by, the Company or any Affiliate of the Company will be deemed not to be outstanding, and (b) votes will be determined in accordance with the provisions of the Security Agreement. In determining whether the Trustee shall be protected in relying upon such direction, only Securities which a Responsible Officer of the Trustee knows to be so owned by the Company or an Affiliated shall be so disregarded.

“Collateral” means all collateral of whatsoever nature purported to be subject to the Lien imposed by any Security Document.

“Collateral Agent” means The Bank of New York Mellon, in its capacity as Collateral Agent under the Security Documents, together with its successors in such capacity.

“Discharge Date” has the meaning given to that term in the Security Agreement.

“Effective Time” means 10:00 a.m. (New York City Time) on August 4, 2008.

“International Registry” has the meaning given to that term in the Security Agreement.

“Lien” means, with respect to any asset, any mortgage, lien, pledge, charge, security interest or encumbrance of any kind in respect of such asset, whether or not filed, recorded or otherwise perfected under applicable law, including any conditional sale or other title retention agreement, any lease in the nature thereof, any option or other agreement to sell or give a security interest.

“Permitted Lien” has the meaning given to that term in the Security Agreement.

8

“Security Agreement” means that certain Security and Collateral Agency Agreement, dated as of July 30, 2008 by and among the Company, the Guarantor and the Collateral Agent on behalf of and for the benefit of the Holders of Securities.

“Security Documents” means the Security Agreement and all other security agreements, pledge agreements, collateral assignments, mortgages, deeds of trust, collateral agency agreements, control agreements or other grants or transfers for security executed and delivered by the Company or Guarantor creating (or purporting to create) a Lien upon Collateral in favor of the Collateral Agent, in each case, as amended, modified, renewed, restated or replaced, in whole or in part, from time to time. “

“UCC” means the Uniform Commercial Code as in effect in the State of New York or any other applicable jurisdiction.

Section 2.5 Conforming Amendments Regarding Additional Article XIV. The following provisions of the Indenture are hereby amended as follows:

“Neither the Company nor the Guarantor will take or omit to take any action which would materially and adversely affect or impair the Liens in favor of the Collateral Agent, on behalf of itself, the Trustee and the Securityholders, with respect to the Collateral. Neither the Guarantor or the Company shall grant to any Person, or permit any Person to retain (other than the Trustee and the Collateral Agent), any interest whatsoever in the Collateral, except Permitted Liens. The Company shall, and shall cause the Guarantor to, at their sole cost and expense, execute and deliver all such agreements and instruments as the Collateral Agent or the Trustee shall reasonably request to more fully or accurately describe the property intended to be Collateral or the obligations intended to be secured by the Security Documents. The Company shall, and shall cause the Guarantor to, at its sole cost and expense, file any such notice filings or other agreements or instruments as may be reasonably necessary or desirable under applicable law to perfect the Liens created by the Security Documents at such times and at such places as the Collateral Agent or the Trustee may reasonably request.”

9

“(8) except as permitted by this Indenture, any Security Document is held in any judicial proceeding to be unenforceable or invalid or ceases for any reason to be in full force and effect, or the Company or Guarantor, or any Person acting on behalf of the Company or Guarantor, denies or disaffirms its obligations under the Security Document to which it is a party or shall cease to grant the Holders any right or Lien in Collateral.”

In addition, the word “or” shall be deleted from the end of clause (6) of Section 6.01 of the Indenture and at the end of clause (7) of Section 6.01 of the Indenture the period shall be deleted and replaced with “; or”.

“The Securities are secured obligations of the Company, secured by a pledge of Collateral (as defined in the Indenture) pursuant to the Security Documents referred to in the Indenture. The Securities are limited to $143,750,000 aggregate Principal Amount.”

Section 2.6 Execution of Additional Agreement. The Company and the Guarantor shall execute and deliver a Security and Collateral Agency Agreement substantially in the form of Exhibit A hereto.

ARTICLE THREE

EFFECTIVENESS

Section 3.1 Conditions to the Effectiveness of this First Supplemental Indenture. This First Supplemental Indenture will become effective upon the execution of a counterpart hereof by each of the parties hereto and receipt by each party of written notification of such execution and written or telephonic authorization of delivery thereof; provided, that if the Company fails to deposit with the Paying Agent prior to the Effective Time the consideration sufficient to pay the Repurchase Price of all the Securities or portions thereof that are to be purchased as of the Repurchase Date occurring on August 1, 2008, as provided in Section 3.11 of the Indenture, then this First Supplemental Indenture shall be null and void and of no effect.

10

ARTICLE FOUR

MISCELLANEOUS PROVISIONS

Section 4.1 Execution as Supplemental Indenture. This First Supplemental Indenture is executed and shall be construed as an indenture supplemental to the Indenture and, as provided in the Indenture, this First Supplemental Indenture forms a part thereof.

Section 4.2 Responsibility for Recitals, etc. The recitals herein shall be taken as the statements of the Company, and the Trustee assumes no responsibility for the correctness thereof. The Trustee makes no representations as to the validity or sufficiency of this First Supplemental Indenture.

Section 4.3 Provisions Binding on Company’s and Guarantor’s Successors. All of the covenants, stipulations, promises and agreements made in this First Supplemental Indenture by the Company shall bind its successors and assigns and those of the Guarantor whether so expressed or not.

Section 4.4 Governing Law. This First Supplemental Indenture shall be deemed to be a contract made under the laws of the State of New York and, for all purposes, shall be construed in accordance with the laws of said State.

Section 4.5 Securities Deemed Conformed. As of the date hereof, the provisions of each Security then outstanding shall be deemed conformed, without the necessity of any reissuance or exchange of such Security or any other action on the part of the Securityholders, the Company or the Trustee, so as to reflect this First Supplemental Indenture.

Section 4.6 Execution and Counterparts. This First Supplemental Indenture may be executed in any number of counterparts, each of which shall be an original, but such counterparts shall together constitute but one and the same instrument.

Section 4.7 Trust Indenture Act to Control. If and to the extent that any provision of this First Supplemental Indenture limits, qualifies, or conflicts with another provision included in the Indenture or in this First Supplemental Indenture that is required to be included in or is or is deemed to be applicable to this First Supplemental Indenture by any of Sections 310 to 317, inclusive, of the Trust Indenture Act of 1939, such required other applicable provision shall control.

Section 4.8 Certain Duties and Responsibilities of the Trustee. In entering into this First Supplemental Indenture, the Trustee shall be entitled to the benefit of every provision of the Indenture relating to the conduct or affecting the liability or affording protection to the Trustee, whether or not elsewhere herein so provided.

11

Section 4.9 Ratification of Indenture; Supplemental Indenture Part of Indenture. Except as expressly amended hereby, the Indenture, as amended and supplemented, is in all respects ratified and confirmed and all the terms, conditions and provisions thereof shall remain in full force and effect. This First Supplemental Indenture shall form a part of the Indenture for all purposes, and every Securityholder heretofore or hereafter authenticated and delivered shall be bound hereby.

[signature page follows]

12

IN WITNESS WHEREOF, the parties hereto have caused this First Supplemental Indenture to be duly executed, all as of the day and year first above written.