NAVIGANT INTERNATIONAL, INC. and WELLS FARGO BANK, NATIONAL ASSOCIATION (successor by merger to Wells FargoBank Minnesota, N.A.) Trustee

Exhibit 10.1

NAVIGANT INTERNATIONAL, INC.

and

WELLS FARGO BANK, NATIONAL ASSOCIATION

(successor by merger to Wells Fargo Bank Minnesota, N.A.)

Trustee

First Supplemental Indenture

Dated as of July 22, 2005

to the Indenture dated as of November 7, 2003

FIRST SUPPLEMENTAL INDENTURE, dated as of July 22, 2005 (the “Effective Time”), between NAVIGANT INTERNATIONAL, INC., a Delaware corporation (the “Company”), and WELLS FARGO BANK, NATIONAL ASSOCIATION (successor by merger to Wells Fargo Bank Minnesota, N.A.), as trustee (the “Trustee”).

RECITALS OF THE COMPANY

WHEREAS, the Company has duly issued its 4.875% Convertible Subordinated Debentures due 2023 in the aggregate principal amount of $72,000,000 (the “Debentures”) pursuant to an Indenture dated as of November 7, 2003, between the Company and the Trustee (the “Indenture”), and the Debentures are outstanding on the date hereof;

WHEREAS, the Trustee delivered to the Company on May 23, 2005, a notice that the Company was not in compliance with Sections 5.08 and 6.04 of the Indenture;

WHEREAS, the Company is amending the Indenture to amend the reporting requirements in Sections 5.08 and 6.04 of the Indenture and to amend the conversion provisions in Section 15 of the Indenture;

WHEREAS, the Company on July 21, 2005 has received the written consents from holders (as defined in the Indenture) of a majority in aggregate principal amount of the outstanding (as defined in the Indenture) Debentures to certain amendments and waivers to the Indenture upon the terms and subject to the conditions set forth in the Company’s Consent Solicitation Statement dated June 23, 2005 and the accompanying Consent Form (with any amendments);

WHEREAS, Section 11.02 of the Indenture provides that, with the consent of the holders of a majority in aggregate principal amount of the outstanding Debentures, the Company and the Trustee may enter into an indenture supplemental to the Indenture for the purpose of amending, modifying or changing the Indenture or the Debentures;

WHEREAS, Section 7.07 of the Indenture provides that the holders of a majority in aggregate principal amount of the outstanding Debentures may waive any past default or Event of Default under the Indenture and its consequences;

WHEREAS, the Board of Directors of the Company has by resolution dated June 24, 2005 authorized the execution and delivery of this First Supplemental Indenture dated July 22, 2005 (the “Supplemental Indenture”);

WHEREAS, Section 11.03 of the Indenture provides that a supplemental indenture becomes effective in accordance with its terms and thereafter binds every Holder;

1

NOW, THEREFORE, the parties hereto agree as follows:

ARTICLE 1

DEFINITIONS AND OTHER PROVISIONS OF GENERAL APPLICATION

SECTION 1.01 Effective Time. This Supplemental Indenture with respect to the Debentures is effective as of the Effective Time.

SECTION 1.02 Provisions of the Indenture. Except insofar as herein otherwise expressly provided, all the definitions, provisions, terms and conditions of the Indenture shall remain in full force and effect. The Indenture, as amended and supplemented by this Supplemental Indenture, is in all respects ratified and confirmed, and the Indenture and this Supplemental Indenture shall be read, taken and considered as one and the same instrument for all purposes and every holder of Debentures authenticated and delivered under the Indenture shall be bound hereby.

SECTION 1.03 Definitions. For all purposes of the Indenture relating to the Debentures amended hereby, except as otherwise expressly provided or unless the subject matter or context otherwise requires:

(1) any reference to an “Article” or a “Section” refers to an Article or Section, as the case may be, of this Supplemental Indenture;

(2) the terms defined in Article 2 have the meanings assigned to them in that Article and include the plural as well as the singular;

(3) each capitalized term that is used in this Supplemental Indenture but not defined herein shall have the meaning specified in the Indenture;

(4) all other terms used herein which are defined in the Trust Indenture Act, either directly or by reference therein, or defined by the rules of the Securities and Exchange Commission and not otherwise defined herein, have the meanings assigned to them therein;

(5) the word “including” (and with correlative meaning “include”) means including, without limiting the generality of, any description preceding such term; and

(6) the words “herein,” “hereof” and “hereunder” and other words of similar import refer to the Indenture as a whole and not to any particular Article, Section or other subdivision.

ARTICLE 2

AMENDMENT TO ARTICLE 1 OF THE INDENTURE

SECTION 2.01 Amendment of Definitions. Section 1.01 of the Indenture is hereby amended by inserting the following terms:

“10-K Extended Delivery Deadline” means October 31, 2005.

2

“10-Q Extended Delivery Deadline” means November 9, 2005.

“2004 Annual Report” means the Company’s Annual Report on Form 10-K for the year ended December 26, 2004.

“2005 10-Q Reports” means the Quarterly Report on Form 10-Q for the fiscal quarter ended March 27, 2005 and the fiscal quarter ending June 26, 2005.

“Amendment and Waiver” means the amendments to Sections 5.08 and 6.04 set forth in Article 3 of the First Supplemental Indenture dated as of July 22, 2005 and the waiver of compliance with Sections 5.08 and 6.04 set forth in the Consent Form executed by the holders of a majority in the aggregate principal amount of the outstanding Debentures.

“Change of Control” means the occurrence of the events in the first clauses (i) and (ii) of the definition of Fundamental Change below, disregarding the exceptions in the second clauses (i) and (ii) in such definition.

“Filing Covenant Reversion Date” means, with respect to the Debentures, the earliest of 5:30 p.m., New York City time, on (i) the Business Day following the Company’s failure to file with the Trustee the 2004 Annual Report by the 10-K Extended Delivery Deadline and (ii) the Business Day following the Company’s failure to file with the Trustee the 2005 10-Q Reports by the 10-Q Extended Delivery Deadline.

“Solicitation Documents” means the Consent Solicitation Statement dated as of June 23, 2005 and the related Consent Form, each as may be amended and supplemented from time to time.

“Stock Price” means the price per share of Common Stock paid in connection with a Change of Control transaction, which shall be equal to (i) if holders of Common Stock receive only cash in such Change of Control transaction, the cash amount paid per share of Common Stock and (ii) in all other cases, the average of the Last Reported Sale Prices of the Common Stock on each of the five Trading Days prior to, but not including, the effective date of such Change of Control transaction.

“Voting Stock” of a Person means capital stock of such Person of the class or classes pursuant to which the holders thereof have the general voting power under ordinary circumstances to elect at least a majority of the board of directors, managers or trustees of such Person (irrespective of whether or not at the time capital stock of any other class or classes shall have or might have voting power by reason of the happening of any contingency).

3

ARTICLE 3

AMENDMENT TO SECTIONS 5.08 AND 6.04 OF THE INDENTURE

SECTION 3.01 Amendment of Section 5.08. Section 5.08 of the Indenture is hereby amended by inserting the following sentence at the end of the first paragraph of such Section:

“Notwithstanding any of the foregoing, the failure of the Company to comply with this Section 5.08 of this Indenture during the period beginning on April 26, 2005 and ending at 5:30 p.m., New York City time on the 10-K Extended Delivery Deadline shall not constitute a default of this Section 5.08; provided, however, that any foregoing failure to comply with Section 5.08 of this Indenture shall constitute a default as of the 10-K Extended Delivery Deadline if, as of 5:30 p.m., New York City time on the 10-K Extended Delivery Deadline, the Company shall have failed to provide the Trustee with the compliance certificate for fiscal year 2004.”

SECTION 3.02 Amendment of Section 6.04. Section 6.04 of the Indenture is hereby amended by inserting the following sentence at the end of such Section:

“Notwithstanding any of the foregoing, the failure of the Company to comply with this Section 6.04 of this Indenture or §314 of the Trust Indenture Act during the period beginning on April 12, 2005 and ending at 5:30 p.m., New York City time on the Filing Covenant Reversion Date shall not constitute a default of this Section 6.04; provided, however, that any foregoing failure to comply with Section 6.04 of this Indenture or §314 of the Trust Indenture Act shall constitute a default as of the Filing Covenant Reversion Date if, as of 5:30 p.m., New York City time on the Filing Covenant Reversion Date, the Company shall have failed to (i) file the 2004 Annual Report by the 10-K Extended Delivery Deadline with the SEC and (ii) file the 2005 10-Q Reports with the SEC by the 10-Q Extended Delivery Deadline in a form that causes the Company to be current in all material respects in its filing obligations under the Exchange Act.”

ARTICLE 4

AMENDMENTS TO SECTION 15 OF THE INDENTURE AND ADDITION OF EXHIBIT

SECTION 4.01 Amendment of Section 15.01(b)(ii). Section 15.01(b)(ii) is hereby amended to replace such provision in its entirety with the following:

4

SECTION 4.02 Amendment of Section 15.01. Section 15.01 of the Indenture is hereby amended by inserting the following sections:

“(d) If and only to the extent a holder timely elects to convert Debentures in connection with (a) a Change of Control specified in Section 15.01(b)(ii) that occurs prior to November 1, 2010, and 10% or more of the consideration for the Common Stock in such Change of Control transaction consists of consideration other than common stock traded or scheduled to be traded immediately following such transaction on a U.S. national securities exchange or the Nasdaq National Market, then the Conversion Rate shall be increased by an additional number of shares of Common Stock (the “Additional Shares”) as described below; provided, that, if the Stock Price paid in connection with such transaction is greater than $60.00 or less than $13.35 (subject in each case to adjustment as described below), no Additional Shares shall be added to the Conversion Rate. Notwithstanding this Section 15.01(d), if the Company elects to adjust the Conversion Rate pursuant to Section 15.01(e), the provisions of Section 15.01(e) shall apply in lieu of the provisions of this Section 15.01(d). The Company shall notify holders, at least twenty (20) days prior to the anticipated effective date of such transaction causing any increase of the Conversion Rate pursuant to this Section 15.01(d), whether the Company elects to increase the Conversion Rate as described above or to adjust the Conversion Rate pursuant to Section 15.01(e).

5

The number of Additional Shares to be added to the Conversion Rate as described in the immediately preceding paragraph shall be determined by reference to the table attached as Exhibit B hereto, based on the effective date of such Change of Control transaction specified in Section 15.01(b)(ii) and the Stock Price paid in connection with such transaction; provided, that, if the Stock Price is between two Stock Price amounts in the table or such effective date is between two effective dates in the table, the number of Additional Shares shall be determined by a straight-line interpolation between the number of Additional Shares set forth for the higher and lower Stock Price amounts and the two dates, as applicable, based on a 360-day year. The “effective date” with respect to a Change of Control transaction specified in Section 15.01(b)(ii) means the date that such transaction or event becomes effective.

With respect to any Debentures tendered for conversion to which Additional Shares apply, any shares of Common Stock to be delivered upon conversion of such Debentures pursuant to Section 15.02 shall be delivered to holders who elect to convert their Securities on the third Business Day following the date the settlement amount is determined.

The Stock Prices set forth in the first row of the table in Exhibit B hereto shall be adjusted as of any date on which the Conversion Rate of the Debentures is adjusted pursuant to Section 15.05. The adjusted Stock Prices shall equal the Stock Prices applicable immediately prior to such adjustment, multiplied by a fraction, the numerator of which is the Conversion Rate immediately prior to the adjustment giving rise to the Stock Price adjustment and the denominator of which is the Conversion Rate as so adjusted. The number of Additional Shares shall be adjusted in the same manner as the Conversion Rate as set forth in Section 15.05.

Notwithstanding the foregoing, in no event shall the total number of shares of Common Stock issuable upon conversion of the Securities exceed 74.9063 per $1,000 principal amount of Securities, subject to adjustments in the same manner as the Conversion Rate as set forth in Section 15.05.

(e) Notwithstanding the provisions of Section 15.01(d), in the case of a Change of Control that would lead to the issuance of Additional Shares as set forth in clause (d) above that is also a Public Acquirer Change of Control, the Company may, in lieu of increasing the Conversion Rate by Additional Shares as described in Section 15.01(d), elect to adjust the Conversion Rate and the related Conversion Obligation such that from and after the effective date of such Public Acquirer Change of Control, holders of Debentures shall be entitled to convert their Debentures (subject to the satisfaction of the conditions to conversion set forth in Section 15.01(a)) into Public Acquirer Common Stock. The Conversion Rate following the effective date of such transaction will be a number of shares of Public Acquirer Common Stock equal to the product of the Conversion Rate in effect immediately before the Public Acquirer Change of Control times the average of the quotients obtained, for each Trading Day in the 10 consecutive Trading Day period ending on the Trading Day immediately preceding the effective date of such Public Acquirer Change of Control (the “Valuation Period”), of:

6

The “Acquisition Value” of the Common Stock means, for each Trading Day in the Valuation Period, the value of the consideration paid per share of Common Stock in connection with such Public Acquirer Change of Control, as follows:

“Public Acquirer Change of Control” means an event constituting a corporate transaction that would otherwise obligate the Company to increase the Conversion Rate as described in Section 15.01(d) and the acquirer, the Person formed by or surviving the merger or consolidation or any entity that is a direct or indirect “beneficial owner” (as defined in Rule 13d-3 under the Exchange Act) of more than 50% of such Person’s or Acquirer’s Voting Stock, has a class of common stock traded on a national securities exchange or quoted on a U.S. national securities exchange or quoted on the National Association of Securities Dealers Automated Quotation System or which will be so traded or quoted when issued or exchanged in connection with such corporate transaction (the “Public Acquirer Common Stock”); provided, that, if, there is more than one of such entity, the relevant entity shall be such entity with the most direct beneficial ownership to such acquirer’s or Person’s capital stock.

In addition, the Public Acquirer Change of Control shall be deemed to be an event meeting the condition of Section 15.01(a)(iii) and, for such event, the holder can pursuant to Section 15.01(a) convert the Debentures upon the Public Acquirer Change of Control at the adjusted Conversion Rate described above (not the increased Conversion Rate described in Section 15.01(d)) during the period specified in Section 15.01(b)(ii). In addition, the holders can also, subject to certain conditions, require the Company to repurchase all or a portion of their Debentures as described in Section 3.05.

SECTION 4.03 Amendment of Section 15.02(h). Section 15.02(h) is hereby amended to add subsection (v):

“(v) If a holder tenders Debentures for conversion and the Conversion Obligation is being determined at a time when the Debentures are convertible into Exchange Property, the Conversion Obligation of each Debenture shall be determined

7

based on the kind and amount of such Exchange Property and the value thereof during the Cash Settlement Averaging Period. Settlement of Debentures tendered for conversion after the effective date of any transaction giving rise to Exchange Property shall be as set forth above.

For the purposes of this Section, the Last Reported Sale Price of the Common Stock shall be deemed to equal the sum of (A) 100% of the value of any Exchange Property consisting of cash received per share of Common Stock, (B) the Last Reported Sale Price of any Exchange Property received per share of Common Stock consisting of securities that are traded on a U.S. national securities exchange or approved for quotation on the Nasdaq National Market and (C) the Fair Market Value of any other Exchange Property received per share, as determined by two independent nationally recognized investment banks selected by the Company for this purpose. Settlement (in cash and/or shares) will occur on the third Business Day following the date the settlement amount is determined.”

SECTION 4.04 Addition of Exhibit. The Indenture is hereby amended to add Annex I attached hereto as Exhibit B to the Indenture.

ARTICLE 5

CONDITIONS TO EFFECTIVENESS

This Supplemental Indenture shall become effective on the date when each of the conditions set forth in this Article 5 to this Supplemental Indenture shall have been fulfilled to the satisfaction of the Trustee.

SECTION 5.01 Delivery of Officers’ Certificate and Opinion of Counsel. The Trustee shall have received the Officers’ Certificate and Opinion of Counsel required pursuant to Sections 11.05 and 16.06 of the Indenture.

SECTION 5.02 Payment of Fees and Expenses. The Company shall have paid all of the Trustee’s fees and expenses (including the fees and expenses of Faegre & Benson LLP) incurred in connection with the preparation, negotiation and execution of this Supplemental Indenture and other matters relating to the Indenture.

SECTION 5.03 Consent of Debenture Holders. The Trustee shall have reviewed executed Consent Forms as required by Section 9.02 of the Indenture from holders of a majority in aggregate principal amount of the outstanding Debentures.

SECTION 5.04 Effectiveness of Form T-3. The Securities and Exchange Commission shall have declared effective, prior to the Expiration Time, the Form T-3 for qualification of the Indenture, as amended, under the Trust Indenture Act of 1939.

ARTICLE 6

MISCELLANEOUS

SECTION 6.01 Integral Part. This Supplemental Indenture constitutes an integral part of the Indenture.

8

SECTION 6.02 Adoption, Ratification and Confirmation. The Indenture, as supplemented and amended by this Supplemental Indenture, is in all respects hereby adopted, ratified and confirmed, and this Supplemental Indenture shall be deemed part of the Indenture in the manner and to the extent herein and therein provided. The provisions of this Supplemental Indenture shall, subject to the terms hereof, supersede the provisions of the Indenture to the extent the Indenture is inconsistent herewith.

SECTION 6.03 Counterparts. This Supplemental Indenture may be executed in any number of counterparts, each of which so executed shall be deemed to be an original, but all such counterparts shall together constitute but one and the same instrument.

SECTION 6.04 Governing Law. THE INDENTURE SHALL BE GOVERNED BY AND CONSTRUED IN ACCORDANCE WITH THE LAWS OF THE STATE OF NEW YORK.

SECTION 6.05 Conflict of Any Provision of Indenture with Trust Indenture Act. If and to the extent that any provision of the Indenture limits, qualifies or conflicts with a provision required under the terms of the Trust Indenture Act, the Trust Indenture Act provision shall control.

SECTION 6.06 Effect of Headings. The Article and Section headings herein are for convenience only and shall not affect the construction hereof.

SECTION 6.07 Severability of Provisions. In case any provision in the Indenture or in the Debentures shall be invalid, illegal or unenforceable, the validity, legality and enforceability of the remaining provisions shall not in any way be affected or impaired thereby.

SECTION 6.08 Successors and Assigns. All covenants and agreements in the Indenture by the parties hereto shall bind their respective successors and assigns and inure to the benefit of their respective successors and assigns, whether so expressed or not.

SECTION 6.09 Benefit of Indenture. Nothing in this Supplemental Indenture, express or implied, shall give to any Person, other than the parties hereto, any Debenture Registrar, any Paying Agent, and their successors hereunder, and the holders of the Debentures, any benefit or any legal or equitable right, remedy or claim hereunder or under the Indenture.

9

SECTION 6.10 Acceptance by Trustee. The Trustee, based on the Officers’ Certificate and Opinion of Counsel delivered pursuant to Section 11.05 of the Indenture, accepts the amendments to the Indenture effected by this Supplemental Indenture and agrees to execute the trusts created by the Indenture as hereby amended, but only upon the terms and conditions set forth in this Supplemental Indenture and the Indenture. Without limiting the generality of the foregoing, the Trustee assumes no responsibility for the correctness of the recitals contained herein, which shall be taken as the statements of the Company and except as provided in the Indenture the Trustee shall not be responsible or accountable in any way whatsoever for or with respect to the validity or execution or sufficiency of this Supplemental Indenture or the Solicitation Documents and the Trustee makes no representation with respect thereto. All rights, protections, privileges, indemnities and benefits granted or afforded to the Trustee under the Indenture shall be deemed incorporated herein by this reference and shall be deemed applicable to all actions taken, suffered or omitted by the Trustee under this Supplemental Indenture.

IN WITNESS WHEREOF, the parties hereto have caused this First Supplemental Indenture to be duly executed, and their respective corporate seals to be hereunto affixed and attested, all as of the day and year first above written.

Annex I

Exhibit B

Make-Whole Provision

Navigant International, Inc.

Conversion Rate Adjustment Table