FIRST SUPPLEMENTAL INDENTURE

EXHIBIT 4.1

FIRST SUPPLEMENTAL INDENTURE

This FIRST SUPPLEMENTAL INDENTURE (this “Supplement”) is entered into as of June 26, 2006, by and among NEXTEL PARTNERS, INC., a Delaware corporation (the “Company”), and THE BANK OF NEW YORK TRUST COMPANY, N.A., successor to The Bank of New York, as trustee (the “Trustee”).

R E C I T A L S:

WHEREAS, the Company and the Trustee are parties to that certain Indenture, dated as of May 13, 2003 (the “Indenture”), relating to those certain 1 ¹/2% Convertible Senior Notes Due 2008 (the “Notes”);

WHEREAS, in October 2005, the stockholders of the Company elected to exercise the put right set forth in the Company’s Restated Certificate of Incorporation requiring Nextel WIP Corp., a wholly owned subsidiary of Sprint Nextel Corporation (“Nextel WIP”), to acquire all of the outstanding shares of the Company’s Class A Common Stock (the “Put”);

WHEREAS, on June 26, 2006, the Company and Nextel WIP consummated the Put through a redemption by the Company of the outstanding shares of Class A Common Stock of the Company for a cash payment of $28.50 per share;

WHEREAS, pursuant to Section 14.06 of the Indenture, the Company is amending the Indenture to change the conversion rights of the Notes from the right to receive Class A Common Stock into the right to receive an amount in cash equal to $28.50 – the same per share amount as the cash payment made in connection with the Put to holders of Class A Common Stock – for each share of Class A Common Stock into which the Notes were previously convertible; and

WHEREAS, pursuant to Section 10.01 of the Indenture, the Trustee is authorized to execute and deliver this Supplement without the consent of the Noteholders.

NOW, THEREFORE, in consideration of the premises contained herein, and for other good and valuable consideration, the receipt and sufficiency of which are hereby acknowledged, the parties hereto agree as follows:

1. Defined Terms. Capitalized terms used and not otherwise defined herein have the respective meanings assigned to such terms in the Indenture.

2. Adjustment to Conversion Privilege. The Indenture and the Notes are hereby amended in all respects necessary so that the holder of a Note, from and after the date of this Supplement, on the terms and subject to the conditions set forth in the Indenture, shall have the right, at such holder’s option, to convert each $1,000 principal amount of the Notes into an amount in cash equal to $3 ###-###-#### in lieu of shares of Common Stock, by (a) surrender of the Note so to be converted in whole or in part, together with any required funds and original or facsimile of a conversion notice in the form attached hereto as “Amended Conversion Notice” or (b) in the case of an interest in a Global Note, completion of the appropriate instruction form for conversion pursuant to the Depositary’s book entry conversion program and delivery by book-entry of such interest in the Global Note, together with any required endorsements, transfer documents and funds, and in the case of both (a) and (b) under the circumstances and other conditions described in the Indenture. Notwithstanding anything to the contrary in the Indenture or this Supplement, from and after 5:00 p.m. (New York City time) on June 26, 2006, no holder of Notes will have any right to convert Notes into shares of Common Stock.

3. Conditions to Effectiveness. This Supplement shall be effective upon execution and delivery of this Supplement by the Company and the Trustee.

4. Miscellaneous.

4.1 Effect; Ratification.

(a) Upon and after the effectiveness of this Supplement, each reference in the Indenture to “this Indenture,” “hereunder,” “hereof” or words of like import referring to the Indenture, and each reference in the Notes issued prior to the date hereof to “the Indenture,” “thereunder,” “thereof” or words of like import referring to the Indenture, shall mean and be a reference to the Indenture as amended hereby.

(b) Upon and after the effectiveness of this Supplement, each reference in the Indenture to the Notes, and each reference in the Notes issued prior to the date hereof referring to the Notes, shall mean and be a reference to the Notes as amended hereby.

(c) Except as specifically amended above, the Indenture and the Notes issued prior to the date hereof are and shall continue to be in full force and effect and are hereby in all respects ratified and confirmed.

(d) The execution, delivery and effectiveness of this Supplement shall not, except as expressly provided herein, operate as a waiver of any right, power or remedy of the Company, any Noteholder or the Trustee under the Indenture or any of the Notes, or constitute a waiver or amendment of any provision of the Indenture or any of the Notes.

4.2 Execution in Counterparts. This Supplement may be executed in any number of counterparts, each of which shall be an original, but such counterparts shall together constitute one and the same instrument.

2

4.3 Headings. The headings of the paragraphs of this Supplement have been inserted for convenience of reference only, are not to be considered a part hereof, and shall in no way modify or restrict any of the terms or provisions hereof.

4.4 Severability. In case any provision in this Supplement shall be invalid, illegal or unenforceable, then (to the extent permitted by law) the validity, legality and enforceability of the remaining provisions shall not in any way be affected or impaired thereby.

4.5 Governing Law. This Supplement shall be deemed 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 the State of New York, without regard to conflicts of laws principals thereof.

4.6 Trustee Not Responsible for Recitals. The recitals contained herein shall be taken as the statements of the Company and the Trustee makes no representation as to the validity or sufficiency of this Supplement.

[Signature Page Follows]

3

IN WITNESS WHEREOF, the parties hereto have executed this Supplement as of the date first above written.

AMENDED CONVERSION NOTICE

THE BANK OF NEW YORK

The undersigned registered owner of this Note hereby irrevocably exercises the option to convert this Note, or the portion thereof (which is $1,000 or an integral multiple thereof) below designated, in accordance with the terms of the Indenture referred to in this Note, into an amount of cash equal to $3 ###-###-#### for each $1,000 in principal amount of Notes converted and directs that a check for payment thereof, and any Notes representing any unconverted principal amount hereof, be issued and delivered to the registered holder hereof unless a different name has been indicated below. Capitalized terms used herein but not defined shall have the meanings ascribed to such terms in the Indenture. If a check for payment is to be issued in favor of, or any Notes issued for any portion of this Note not converted are to be issued in the name of, a person other than the undersigned, the undersigned will provide the appropriate information below and pay all transfer taxes payable with respect thereto. Any amount required to be paid by the undersigned on account of interest accompanies this Note.

Fill in the information for the check to be issued, and Notes if to be delivered, other than to and in the name of the registered holder:

(Name)

(Street Address)

(City, State and Zip Code)

Please print name and address

Principal amount to be converted

(if less than all):

$             

Social Security or Other Taxpayer

Identification Number: