<PAGE>

                                                                   Exhibit 10.38

                              EMPLOYMENT AGREEMENT

            EMPLOYMENT AGREEMENT, dated as of January 29, 1999, between Nextel
Partners Operating Corp., a Delaware corporation (the "Company"), and Mark P.
Fanning ("Executive"). Capitalized terms used and not otherwise defined herein
shall have the meanings given to such terms in Section 9 or as otherwise set
forth below.

            WHEREAS, the Company desires to employ Executive and to enter into
an agreement embodying the terms of such employment (this "Agreement"), and
Executive desires to accept such employment and enter into this Agreement.

            NOW, THEREFORE, in consideration of the mutual covenants herein
contained, the Company and Executive, intending to be legally bound, hereby
agree as follows:

            1. Employment. (a) Agreement to Employ. Upon the terms and subject
to the conditions hereof the Company shall employ Executive as Vice President -
People Development of the Company until the Expiration Date (as defined in
Section 1(b)), any date to which this Agreement shall have been extended
pursuant to Section 1(b) or any earlier termination of this Agreement pursuant
to Section 6. Executive's office shall be located in the Seattle, Washington
metropolitan area. During the term of his employment hereunder, Executive will
devote substantially all of his business time to the performance of his duties
hereunder.

            (b) Employment Period. Unless earlier terminated pursuant to Section
6, the initial term of Executive's employment with the Company shall be for a
period of four years, commencing on the date of this Agreement and continuing
until January 29, 2003 (the "Expiration Date"). The term of this Agreement may
be extended by the Company for successive one-year terms commencing on the
Expiration Date by providing Executive notice of such election not less than 60
days prior to the Expiration Date or the scheduled expiration date of any
renewal term.

            2. Responsibility. Executive shall be responsible for supervising
the establishment, maintenance and operation of all human resources and
organizational development functions at the Company and for such other duties
commensurate with his position that may be assigned from time to time by the
Board of Directors of the Company (the "Board") or (to the extent not
inconsistent with the duties assigned to him by the Board) by the chief
executive officer of the Company. Executive shall report directly to the chief
executive officer of the Company and shall be subject to the overall supervision
of the Board.

<PAGE>

            3. Compensation and Benefits.

            (a) Salary and Bonus.

                  (i) The Company shall pay Executive a base salary in the
      annual amount of $125,000 payable in accordance with the Company's normal
      payroll practices.

                  (ii) The Company shall (subject to the Board's review and
      approval) establish a performance based program pursuant to which
      Executive shall receive, if performance targets are met, an additional
      annual cash payment of up to forty percent (40%) of Executive's then
      current base salary (or such higher amount as the Board may approve), and
      shall offer to Executive a benefits package equivalent to that provided to
      the Company's other senior executives.

                  (iii) In addition to the amounts payable pursuant to
      paragraphs (i) and (ii) above, in recognition of Executive's services
      prior to the date hereof, the Company will on the date of the Closing make
      a lump sum payment to Executive in the amount of $72,917.

                  (iv) Upon completion of the Required Build on or before the
      Scheduled Completion Date, the Compensation Committee of the Board shall
      review Executive's base salary and bonus payment in light of the
      performance of Executive and the Company, and may, in its discretion,
      increase (but not decrease) such base salary and bonus payment by an
      amount it determines to be appropriate.

                  (v) If this Agreement is renewed by the Company upon
      expiration of the initial four-year term, Executive's base salary and
      bonus payment will be recalculated so as to place them at levels that are
      comparable to prevailing market rates, based on the overall compensation
      packages of executives holding comparable positions in similarly situated
      companies (which shall include consideration of Executive's equity
      compensation arrangements in comparison to those of executives holding
      comparable positions in similarly situated companies).

            (b) Expenses. Executive shall maintain his own automobile and shall
carry liability insurance in the minimum amount of $300,000. The Company shall
reimburse Executive monthly for business use of his automobile at the prevailing
IRS rate per mile. Executive shall also be reimbursed monthly for all other
reasonable out-of-pocket expenses incurred or paid by Executive while
representing the Company or conducting Company business. Executive shall be
responsible for maintaining records reasonably satisfactory to support all
claimed business usage of his automobile and to substantiate all out-of-pocket
expenses incurred for which reimbursement is sought and shall furnish such
records to the Company in accordance with its policies.

            (c) Vacation. Executive shall be entitled to 15 vacation days each
calendar year, any or all of [ILLEGIBLE] unused


                                       2
<PAGE>

vacation time earned through the last completed month of service, computed at
the rate of ten hours per month.

            (d) Indemnification. The Company shall indemnify and hold Executive
harmless in accordance with the terms of the Company's certificate of
incorporation and bylaws, in each case as in effect on the date hereof.

            (e) D&O Insurance. The Company shall maintain directors and officers
liability insurance coverage covering Executive in amounts customary for
similarly situated companies in the telecommunications industry and with
reputable insurers. All such policies shall provide for coverage to Executive on
the same terms and conditions applicable to the coverage provided under such
policies to the Company's other directors and officers.

            4. Nondisclosure of Proprietary and Confidential Information.

            (a) Confidential Information. Executive agrees to refrain (whether
during or after his employment with the Company) from disclosing or using,
except as permitted by this Agreement, any secrets or confidential information
with respect to any Covered Entity, including without limitation its trade
secrets, patents, affairs, business plans, strategic, commercial or financial
information other than information that is or becomes publicly available through
no fault of Executive (the "Confidential Information"). Executive may disclose
or communicate only such information as is reasonably required or specifically
approved by the Board or authorized management personnel of the Company
designated by the Board in connection with Executive's services. Confidential
Information may be used solely for the benefit of the Company, and Executive
shall not make any other use of such information. Executive agrees that all
materials relating to the business of any Covered Entity that are provided or
made available to Executive, or created by Executive, during the course of
Executive's services to the Company shall be and remain the property of the
Company and/or the applicable Covered Entity (subject to the terms of any
separate agreement between the Company and/or its Parent Companies and the
affected Covered Entity), whether or not such materials constitute or contain
Confidential Information, and all copies of such materials shall be returned to
the Company immediately upon the termination of Executive's services to the
Company. In the event that the Company notifies the Executive that it has
entered into a confidentiality agreement with a Covered Entity or with any
Affiliate of the Company with respect to confidential information to be provided
to the Company, the Executive shall comply with such reasonable obligations
thereunder as are applicable to the Executive.

            (b) Innovations; Inventions. Executive hereby sells, transfers and
assigns to the Company all right, title and interest of Executive in and to any
and all inventions, ideas, disclosures and improvements of any kind or nature
whatsoever, whether patented or unpatented, and any and all copyrightable
materials, in either case whether made or conceived in whole or in part by
Executive alone or together with others, from January 1, 1998 to the date of
this Agreement or during the initial term of this Agreement or any renewal term,
that (i) relate to any methods, designs, products, processes, apparatus, service
or devices sold, leased used or under construction or development by the Company
or any of its subsidiaries or affiliates, (ii) relate to the business,


                                       3
<PAGE>

functions or operations of the Company or any of its subsidiaries or affiliates
or (iii) arise from, in whole or in part, the efforts of Executive on behalf of
the Company. Executive will communicate and disclose to the Company promptly all
information, data and details pertaining to any inventions, ideas, disclosures
and improvements described above, in such form or format as the Company may
reasonably request. During the term of this Agreement or any renewal term and
thereafter, Executive will execute, acknowledge or deliver to the Company (at
the Company's expense) such formal transfers and assignments and such other
papers and documents as may be required of Executive to permit the Company to
file and prosecute any patent applications to the Company desires to file and
prosecute relating to any of the foregoing, and, as to copyrightable material,
to obtain copyright thereon.

            5. Non-Competition; Non-Solicitation.

            (a) In view of the unique value to the Company of Executive's
services and because of the Confidential Information to be obtained by or
disclosed to Executive as described above, Executive agrees that, during the
term of this Agreement and for a period of six months thereafter, provided that
this Agreement is not terminated by the Company without Cause or by Executive
for Good Reason:

                  (i) Executive will not directly or indirectly assist or become
      associated with any wireless voice communications service provider in any
      business of such provider that competes in any of the markets of any of
      the Restricted Entities, whether as a principal, partner, employee,
      consultant or shareholder (other than as a holder of less than 5% of the
      outstanding voting shares of any publicly traded company);

                  (ii) Executive will not directly or indirectly solicit for
      employment or employ any employee of any of the Restricted Entities,
      unless such solicited person shall have ceased to be employed by any such
      entity for a period of at least six months; and

                  (iii) Executive will not directly or indirectly, solicit
      business from customers of any of the Restricted Entities, provided that
      the foregoing shall not restrict Executive or any entity with which
      Executive is associated from soliciting or doing business with any
      customer of any of the Restricted Entities, if such solicitation does not
      interfere with any business relationship between such solicited customer
      and any of the Restricted Entities.

            (b) If Executive violates any provision of Section 4 or Section
5(a), the Company shall be entitled to receive from Executive reimbursement for
any and all damages caused by such breach, provided that Executive shall not be
liable for indirect, special, consequential or punitive damages (it being
understood and agreed that this remedy is in addition to, and not a limitation
on, any injunctive relief or other rights or remedies to which the Company is or
may be entitled to at law or in equity). Executive acknowledges and agrees that
the Company's (and as applicable, each Restricted Entity's) remedies at law for
a breach or threatened breach of any provision of Section 4 or Section 5(a)
would be inadequate and, in recognition of this fact, Executive agrees that, in
the


                                       4
<PAGE>

event of such a breach or threatened breach, in addition to any remedies at law,
the Company and, as to Article 4, each Covered Entity and, as to Article 5, each
Restricted Entity, without posting any bond, shall be entitled to obtain
equitable relief in the form of specific performance, temporary restraining
order, temporary or permanent injunction or any other equitable remedy which may
then be available. As provided in Section 10(b) hereof, the equitable remedies
referenced in this Section 5(b) shall be in addition to, and not in substitution
for or exclusion of, any other remedies available at law or in equity for any
breach of either or both of Sections 4 or 5. Executive and the Company each
specifically acknowledge and agree that the provisions of Sections 4 and 5 are
for the express benefit of each Covered Entity (in the case of Section 4) and
each Restricted Entity and that (i) no waiver, amendment or other modification
of Sections 4 or 5 with respect to a Covered Entity or Restricted Entity shall
be effective unless it has been consented to in writing by such Covered Entity
or Restricted Entity, as the case may be, and (ii) each such Covered Entity and
Restricted Entity shall be entitled to enforce the provisions of Section 4
and/or 5 hereof (as appropriate) as fully and with the same rights and effect as
if such Covered Entity or Restricted Entity were a signatory party to this
Agreement.

            (c) If any provisions of Section 4 or Section 5(a) are held to be
invalid or unenforceable, the remaining provisions shall nevertheless continue
to be valid and enforceable as though the invalid or unenforceable parts had not
been included.

            6. Noncontravention. The execution, delivery and performance by
Executive of this Agreement does not and will not (i) violate any applicable
law, rule, regulation, judgment, injunction, order or decree or (ii) require any
consent or other action by any person under, constitute a default under (with
due notice or lapse of time or both), or give rise to any right of termination,
cancellation or acceleration of any right or obligation of Executive or to a
loss of any material benefit to which Executive is entitled under any provision
of any agreement or other instrument binding upon Executive, to the extent that
any of the foregoing would have a material adverse effect on Executive or would
prevent or otherwise render unable Executive to perform his obligations under
this Agreement.

            7. Termination. This Agreement shall automatically terminate (and
the term of this Agreement shall thereupon terminate) upon the occurrence of any
one of the following events:

            (a) Death of Executive.

            (b) If Executive shall have been incapacitated from illness,
accident or other disability and unable to perform his normal duties hereunder
for a cumulative period of three months in any period of six consecutive months,
and no reasonable accommodation being available, upon either party giving the
other party not less than 30 days' written notice.

            (c) The Expiration Date or the scheduled expiration date of any
renewal or extension thereof in compliance with Section 1(b).

            (d) By the Company for Cause.


                                       5
<PAGE>

            (e) By Executive for Good Reason. Upon the occurrence of any event
or the existence of any condition or circumstance constituting Good Reason,
Executive may by notice to the Board, deem a constructive termination of this
Agreement to have occurred, whereupon Executive shall be entitled to the
compensation set forth in Section 7(b).

            (f) Upon not less than 30 days' written notice from Executive to the
Company of his voluntary resignation; provided, that such voluntary resignation
shall not relieve or release Executive from any breach of this Agreement at or
prior to the time of such resignation.

            8. Effect of Termination.

            (a) Upon termination of this Agreement pursuant to Sections 7(a),
(b), (c), (d) or (f) the Company shall compensate Executive (or, in the event of
Executive's death, his surviving spouse, if any, or his estate), for (x) accrued
but unused vacation time, (y) any base salary earned, but unpaid, for services
rendered to the Company on or prior to the date of termination and (z) amounts
which Executive is otherwise entitled to receive under the terms of or in
accordance with any plan, policy, practice or program of, or contract or
agreement with the Company, as in effect immediately prior to the date of such
termination, (including but not limited to the Purchase Agreement), at or
subsequent to the date of termination without regard to the performance by
Executive of further services or the resolution of any contingency, but subject
to any and all rights, remedies and claims of the Company against Executive.

            (b) If Executive resigns for Good Reason or his employment with the
Company is terminated without Cause, the Company shall thereupon pay Executive
the following amounts as severance benefits: (i) all amounts payable pursuant to
Section 8(a), and (ii) a lump sum equal to (x) if Executive resigns for Good
Reason, one year's base salary hereunder plus an amount equal to the most recent
annual bonus, if any, received by Executive pursuant to Section 3(a)(ii) or (y)
if Executive's employment is terminated without Cause, six months' base salary
hereunder plus an amount equal to one-half of the most recent annual bonus, if
any, received by Executive pursuant to Section 3(a)(ii).

            9. Definitions. As used herein, the following terms shall have the
following meanings set forth below:

            "Affiliate" means, with respect to the Company, any person or entity
who or which, directly or indirectly, controls, is controlled by, or is under
common control with, the Company or NPI.

            "Cause" means (i) Executive's conviction of a felony evidencing
criminal dishonesty or moral turpitude, (ii) a willful and material breach of
Executive's duty of loyalty to the Company or its parent Nextel Partners, Inc.
or (iii) after 20 business days following Executive's receipt of written notice
from the Company specifying the particulars in reasonable detail, Executive's
failure to comply with or to cure, as applicable, (A) a willful and material
refusal to comply with specific


                                       6
<PAGE>

written directions of the Board (or specific written directions of the Chief
Executive Officer) consistent with Executive's employment agreement with NPI or
the Company or any of their respective subsidiaries and capable of being
performed by him or (B) a willful and material breach of Executive's duty of due
care to the Company.

            "Class A Common Stock" means the Class A Common Stock, par value
$.001 per share, of NPI.

            "Closing" has the meaning specified in the Purchase Agreement.

            "Covered Entities" means, collectively, the Restricted Entities and
such other entities as may from time to time be reasonably agreed to by the
Company and the Executive to be Covered Entities hereunder.

            "FCC" means the Federal Communications Commission.

            "FCC Modifications" means changes to the agreements relating to the
governance and operation of the Company that are implemented in response to any
assertion or finding by the FCC that such agreements constitute an impermissible
change of control of the FCC licenses made available by NWIP to the Company
thereunder, which changes are implemented in order to cause such agreements to
be in compliance with FCC requirements so as to reflect the intent of the
parties thereto that no impermissible change of control take place.

            "Good Reason" means (i) a material adverse change in Executive's
duties, responsibilities or reporting relationships, (ii) a relocation of
Executive's principal office to a location more than 30 miles away from his then
current office, (iii) a reduction of salary not agreed to by Executive, or
material diminution of other employee benefits (other than any change in
employee benefits approved by the Board and implemented in a non-discriminatory
fashion with respect to all participating employees), or any other material
adverse change in his working conditions, (iv) a material breach by the Company
of other obligations under Executive's employment agreement with the Company or
a subsidiary of the Company that are not cured after 20 business days following
the Company's receipt of a written notification from Executive specifying the
particulars in reasonable detail, and (v) from and after the Closing, following
the implementation of any FCC Modifications, if NWIP exercises control over
day-to-day operating decisions, policy decisions or personnel decisions of the
Company pursuant to such FCC Modifications that (before such modifications)
would have been decisions made by the Company's management and such control
exercised by NWIP is materially more extensive (in the collective reasonable
judgment of the Senior Managers then employed by the Company) than that which
NWIP could have exercised under the agreements to which NWIP is a party relating
to the governance and operation of the Company before giving effect to the FCC
Modifications. Notwithstanding the foregoing, a termination with Good Reason
under clause (v) above shall not be deemed effective until 120 days following
written notice by the Executive to the Company of the occurrence of any of the
foregoing and only if the foregoing continue to occur as of such 120th day.


                                       7
<PAGE>

            "Joint Venture Agreement" means the Joint Venture Agreement, to be
dated the date of the Closing, among Nextel, NPI and the Company.

            "Nextel" means NEXTEL Communications, Inc., a Delaware corporation.

            "NPI" means Nextel Partners, Inc., a Delaware corporation.

            "NWIP" means Nextel WIP Corp., a Delaware corporation and a wholly
owned subsidiary of Nextel.

            "Parent Companies" means NPI and any other entity that directly or
indirectly owns all or substantially all of the Company's outstanding voting
capital stock.

            "Purchase Agreement" means the Restricted Stock Purchase Agreement,
dated as of November 20, 1998, between Executive and the Company.

            "Required Build" means the completion of the build out of all
Initial Sections (as defined in the Joint Venture Agreement) assigned to the
first or second Build Year (as defined in the Joint Venture Agreement), and of
any Option Sections (as defined in the Joint Venture Agreement) assigned to the
first or second Build Year that are included in the Territory (as defined in the
Joint Venture Agreement) through the Company's election under Section 6.2B of
the Joint Venture Agreement, but excluding any such Option Sections that are
included in the Territory (as defined in the Joint Venture Agreement) as a
result of the Company's response to a notice given pursuant to Section 6.2C of
the Joint Venture Agreement.

            "Restricted Entities" means, collectively, the Company, Nextel and
the Parent Companies and their respective subsidiaries.

            "Scheduled Completion Date" means 60 days after December 31, 2001.

            "Senior Managers" means, collectively, John Chapple, John Thompson,
David Thaler, David Aas, Perry Satterlee and Mark Fanning.

            "Shares" means the shares of Class A Common Stock purchased by
Executive pursuant to the Purchase Agreement.

            10. Miscellaneous.

            (a) Merger; Amendment. This Agreement (together with the Purchase
Agreement) constitutes the entire agreement between the parties with respect to
the subject matter hereof, and may be changed, extended or modified only by an
agreement in writing signed by the parties.

            (b) Assignment. The rights and obligations of the Company in this
Agreement shall inure to its benefit and be binding upon its successors in
interest (whether by merger,


                                       8
<PAGE>

consolidation, reorganization, sale of stock or assets or otherwise), provided
that Executive shall not remain bound by this Agreement unless such successor
assumes all of the obligations of the Company hereunder. This Agreement shall
also inure to the benefit of Executive's heirs, executors, administrators and
legal representatives. This Agreement, being for the personal services of
Executive, shall not be assignable by Executive. Certain provisions of Section 4
and 5 of this Agreement are, for the purposes specified therein, intended to
inure to the benefit of certain affiliates of the Company and to be enforceable
separately by them as provided therein.

            (c) Waiver of Breach. The waiver by any party of a breach of any
provision of this Agreement shall not operate or be construed as a waiver of any
subsequent breach by any party.

            (d) Arbitration. Except as otherwise provided herein, any
controversies or claims arising out of, or relating to this Agreement or the
breach thereof, shall be settled by arbitration in accordance with the
commercial rules of the American Arbitration Association, which decision shall
be final and binding on the parties, and judgment upon the award rendered shall
be entered in any court having jurisdiction thereof. Any party may demand such
arbitration in accordance with the procedures set out in those rules. The
arbitration shall be conducted in Seattle, Washington, or such other location as
may be mutually agreed upon by the parties. Special, consequential, or punitive
damages shall not be awarded by the arbitrator. In the event of any arbitration
proceeding hereunder, the Company will (x) pay the fees and expenses of the
arbitrator and (y) advance the Executive's documented out-of-pocket costs
(including reasonable counsel fees and expenses) on a current basis, provided,
that if Executive is determined not to be the substantially prevailing party on
the matters submitted for arbitration (which determination shall be made by the
arbitrator and included in his or her decision), Executive will promptly
reimburse the Company for any expenses so advanced. Executive acknowledges that
the Company is agreeing to make advances to him pursuant to the preceding
sentence in consideration of his agreement to reimburse the Company for any such
advances to the extent required by the preceding sentence. The Company will in
all events pay its own costs (including counsel fees and expenses) in connection
with any arbitration proceeding hereunder.

            (e) Notices. All notices given hereunder shall be in writing and
shall be deemed to have been duly given and received (i) when delivered
personally, with receipt acknowledged in writing by the recipient, (ii) on the
tenth business day alter being sent by registered or certified mail (postage
paid, return receipt requested), (iii) one business day after being sent by a
reputable overnight delivery service, postage or delivery charges prepaid, or
(iv) on the date on which a facsimile is transmitted, in each case to the
parties at their respective addresses stated below; provided, that if the
intended recipient of any notice hereunder refuses to acknowledge receipt
thereof in writing, such notice shall be deemed to have been duly given on the
date of such refusal. Any party may change its address for notice by giving
notice of the new address to the other party in accordance with the provisions
of this paragraph.


                                       9
<PAGE>

                 If to the Company:

                 Nextel Partners Operating Corp.
                 4500 Carillon Point
                 Kirkland, WA 08033
                 Attention: General Counsel
                 Facsimile: 425-828-8098

                 with a copy to:

                 Nextel WIP Corp.
                 1505 Farm Credit Drive
                 McLean, VA 22102
                 Attention: General Counsel
                 Facsimile: 703-394-3496

                 If to Executive:

                 Mark P. Fanning
                 Nextel Partners Operating Corp.
                 4500 Carillon Point
                 Kirkland, WA 98033
                 Facsimile: 425-828-8098

                 and

                 Mark P. Fanning
                 4867 Sunset Beach Road
                 Augurn, NY 13021

            (f) Severability. The invalidity or unenforceability of any
particular provision of this Agreement shall not affect the other provisions
hereof, and the Agreement shall be construed in all respects as though such
invalid or unenforceable provision were omitted.

            (g) Survival. The provisions of Sections 3(d), 4, 5, 8 and 10 shall
survive any termination of this Agreement.

            (h) Governing Law. This Agreement shall be interpreted according to
the internal laws of the State of New York, without regard to choice of law
rules that would result in the application of the laws of another State.

            (i) Remedies Cumulative. All rights, powers and remedies provided
under this Agreement or otherwise available in respect hereof at law or in
equity shall be cumulative and not


                                       10
<PAGE>

alternative, and the exercise or the beginning of the exercise of any thereof by
any party shall not preclude the simultaneous or later exercise of any other
such right, power or remedy by such party.

            (j) Waiver of Jury Trail. EACH OF THE PARTIES HERETO HEREBY
IRREVOCABLY WAIVES ANY AND ALL RIGHT TO TRIAL BY JURY IN ANY LEGAL PROCEEDING
ARISING OUT OF OR RELATED TO THIS AGREEMENT OR THE TRANSACTIONS CONTEMPLATED
HEREBY.

                                      * * *


                                       11
<PAGE>

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

                                            NEXTEL PARTNERS OPERATING CORP.


                                            By /s/ John Chapple
                                               ---------------------------------
                                            Name: John Chapple
                                            Title: President and Chief Executive
                                                                 Officer


                                            ------------------------------------
                                            MARK P. FANNING

<PAGE>

            IN WITNESS WHEREOF. the parties have executed this Agreement as of
the date first above written.

                                            NEXTEL PARTNERS OPERATING CORP.


                                            By /s/ John Chapple
                                               ---------------------------------
                                            Name:
                                            Title:


                                            /s/ Mark P. Fanning
                                            ------------------------------------
                                            MARK P. FANNING