Exhibit 10.1

AGREEMENT

THIS AGREEMENT (the “Agreement”) is made and entered into on February 16, 2006, by and between Richard C. Notebaert (the “Executive”) and Qwest Communications International Inc., a Delaware corporation (together with its wholly owned subsidiaries, the “Company”).

WITNESSETH THAT:

WHEREAS, the Executive and the Company have previously entered into that certain Employment Agreement dated May 14, 2003, as restated on August 19, 2004 and amended on October 21, 2005 and December 16, 2005 (the “Employment Agreement”), pertaining to the employment of the Executive by the Company; and

WHEREAS, the parties desire to provide for the grant of certain non-qualified stock options and shares of restricted stock to the Executive as set forth herein;

NOW, THEREFORE, in consideration of the mutual covenants and agreements set forth below, it is hereby covenanted and agreed by the Executive and the Company as follows:

1.             Stock Option and Restricted Stock Award. The Executive shall be granted options under the Qwest Communications International Inc. Equity Incentive Plan, as amended (the “Equity Incentive Plan”), to acquire shares of the common stock (“Common Stock”) of Qwest Communications International Inc. (“QCII”) and restricted shares of Common Stock under the Equity Incentive Plan, in accordance with the following:

(a)           On February 16, 2006 (the “Grant Date”), the Executive shall be granted non-qualified options to acquire 2,334,000 shares of Common Stock (the “Option Award”). Each option shall have a ten year term commencing on the applicable Grant Date, subject to vesting or earlier forfeiture as provided in subparagraphs (d) and (e) below.

(b)           The option price (“Option Price”) with respect to the 2,334,000 share option granted on the Grant Date is $6.15 per share. Upon the exercise of any such options, the Option Price with respect thereto shall be paid in accordance with the terms and conditions of the Equity Incentive Plan.

(c)           On the Grant Date, the Executive shall be granted 1,459,000 shares of restricted Common Stock (the “Restricted Stock Award”) subject to vesting or forfeiture as provided in subparagraphs (d) and (e) below.

(d)           The Option Award and the Restricted Stock Award shall vest, and the Option Award shall become exercisable on February 16, 2010, if Executive is employed by the Company on such date and if either:

(i)            The closing price for sales of shares of Common Stock made and reported on the New York Stock Exchange or such other national stock exchange on which the Common Stock may then be listed and which constitutes the principal market for the Common Stock (the “Closing Price”) shall have averaged $7.50 per share or

above for any period of 188 consecutive trading days during the period that begins on the Grant Date and ends on the second anniversary of the Grant Date, or

(ii)           The Closing Price shall have averaged $8.00 per share or above for any period of 188 consecutive trading days during the third and fourth years following the Grant Date. If there has been a period of consecutive trading days ending on the second anniversary of the Grant Date where the Closing Price shall have averaged $7.50 per share or above, and there is a period of consecutive trading days starting on the first day of the third year following the Grant Date where the Closing Price shall have averaged $8.00 per share or above, such consecutive trading days shall be added together for purposes of determining whether the requirement of 188 consecutive trading days with an average Closing Price of $8.00 per share or above has been satisfied.

(e)           The Option Award and the Restricted Stock Award shall vest, and the Option Award shall become exercisable prior to February 16, 2010, under the following circumstances:

(i)            If the Executive dies, becomes Disabled, terminates his employment by reason of Constructive Discharge (as defined below), which shall be treated for all purposes of this Agreement as a termination by the Company without Cause, or is terminated by the Company without Cause, during the two year period following the Grant Date, the Restricted Stock Award and the Option Award shall fully vest, and the Option Award shall become exercisable on the date the Executive dies, becomes Disabled or is terminated by the Company without Cause, if at the time of such death, Disability, or termination by the Company without Cause the Closing Price shall have averaged $7.50 per share or above for a period of 22 or more consecutive trading days during the 30 consecutive trading days immediately prior to the date of death, Disability or termination by the Company without Cause. If the Executive dies, becomes Disabled or is terminated by the Company without Cause during the third and fourth years following the Grant Date, the Restricted Stock Award and the Option Award shall fully vest, and the Option Award shall become exercisable on the date the Executive dies, becomes Disabled or is terminated by the Company without Cause, if at the time of such death, Disability or termination by the Company without Cause the Closing Price shall have averaged $8.00 per share or above for a period of 22 consecutive trading days during the 30 consecutive trading days immediately prior to the date of death, Disability or termination by the Company without Cause. If the Executive dies, becomes Disabled or is terminated by the Company without Cause and the provisions of this subparagraph have been satisfied at the time of such event, the Restricted Stock Award and the Option Award shall fully vest, and the Option Award shall become exercisable, on the date of the Executive’s death, Disability or termination by the Company without Cause, or

(ii)           If both of the following conditions ((A) and (B)) have been satisfied prior to the fourth anniversary of the Grant Date, the Restricted Stock Award and the Option Award shall fully vest, and the Option Award shall become exercisable, on the date specified in the immediately following sentence: (A) the approval by a majority of the Incumbent Board (as defined below) of either

2

(1)           a merger, consolidation, reorganization or sale of QCII, or substantially all of its assets in which QCII is not the surviving entity and which results in all of the stockholders of QCII immediately prior to the closing of such transaction receiving cash, marketable securities or a combination of both in exchange for all of their shares of QCII; or

(2)           any other merger, consolidation, reorganization, sale of QCII or its assets, or a transaction in which shares of QCII or cash, or a combination of both, are issued for the acquisition of another company or assets, where the Executive is not offered the continued position of Chairman and CEO of QCII, or if QCII is not the surviving company, the position of Chairman and CEO of the surviving company in such transaction, with the Executive having substantially the same or greater authority, power, responsibility and duties as those contemplated by Sections 1 and 2 of the Employment Agreement and with the same or greater Base Salary and Annual Bonus target and other elements of compensation to which he is entitled under Section 4 of the Employment Agreement at the time of the transaction;

and (B) the closing and consummation of such a transaction. Upon the closing and consummation of a transaction described in clause (A)(1) or (A)(2) (but, in the event of the closing and consummation of a transaction described in (A)(2), only if the Executive has not been offered the position of Chairman and CEO on the terms described in that clause), the Restricted Stock Award and the Option Award shall fully vest, and the Option Award shall become exercisable on the date of the closing and consummation of such transaction. If the Executive dies, becomes Disabled or is terminated by the Company without Cause after the Incumbent Board has approved such a transaction but before the closing and consummation of such transaction, and the Restricted Stock Award and the Option Award otherwise would have vested upon closing under this subparagraph (e)(ii) if the Executive had not died, become Disabled or been terminated without Cause, then the Restricted Stock Award and the Option Award shall fully vest, and the Option Award shall become exercisable, upon the closing and consummation of such transaction.

(f)            Except as otherwise provided in subparagraph (e)(ii) above, unless the termination of the Executive’s employment results in full vesting of the Option Award and Restricted Stock Award in accordance with subparagraphs (e)(i) or (ii) above, the Option Award and the Restricted Stock Award shall be immediately forfeited in the event of a termination of the Executive’s employment for any reason whatsoever, including but not limited to death, voluntary resignation, termination by the Company, or otherwise. If not previously vested, the Option Award and the Restricted Stock Award shall be forfeited on the fourth anniversary of the Grant Date.

(g)           In the event that the Executive resigns from the employ of the Company (other than pursuant to a Constructive Discharge (as defined below) or by reason of a Disability, as defined below)) prior to January 1, 2007, or is terminated by the Company for Cause (as defined below), any vested option or unexercised portion thereof granted under subparagraph (a) above may be exercised, to the extent such option would have been exercisable by the Executive

3

on the date on which the Executive ceased to be an employee, within three months of such date, but in no event later than the date of expiration of the term of the option. In the event of a termination of the Executive’s employment by the Company without Cause or by the Executive by reason of a Constructive Discharge or in the event that the Company does not renew the Employment Agreement in accordance with the provisions of subparagraph 1(a) thereof, any such vested option shall be exercisable for six (6) years following such date of termination of employment, but in no event later than the expiration of the term of the option. In the event of termination of employment due to death or Disability of the Executive while an employee of the Company or in the event of death within not more than three months after the date on which the Executive ceases to be an employee, any such vested option or unexercised portion thereof may be exercised, to the extent exercisable at the date on which the Executive ceased to be an employee, by the Executive or the Executive’s personal representatives, heirs or legatees at any time prior to six (6) years after the date on which the Executive ceased to be an employee, but in no event later than the date of the expiration of the term of the option, and only to the extent that under Section 409A of the Internal Revenue Code of 1986, as amended, this extension of time to exercise would not be viewed as a deferral of compensation.

(h)           In the event of any change in corporate capitalization, such as a stock split, or a corporate transaction, such as any merger, consolidation, separation, including a spin-off, or other distribution of stock or property of QCII, any reorganization (whether or not such reorganization comes with the definition of such term in Section 368 of the Internal Revenue Code) or any partial or complete liquidation of QCII, the number and class of shares subject to options awarded in accordance with subparagraph (a) above, and the Option Price for such options under subparagraph (b) above, shall be adjusted in accordance with the provisions of the Equity Incentive Plan to prevent dilution of the Executive’s rights.

(i)            Options or restricted shares of Common Stock granted in accordance with subparagraph (a) above may be transferred by the Executive to the Executive’s spouse, children or grandchildren (“Immediate Family Members”) or to a trust or trusts for the exclusive benefit of such Immediate Family Members or to a partnership in which such Immediate Family Members are the only partners.

(j)            The Company shall take all steps necessary or desirable to register the shares subject to the foregoing Option Award and the Restricted Stock Award under the Securities Act of 1933, as amended, on a Form S-8 or other appropriate form and to list such shares on the New York Stock Exchange.

(k)           Upon the vesting of any portion of the Restricted Stock Award or the exercise of any portion of the Option Award (other than a cashless exercise involving a same-day sale), the Company shall withhold a number of shares of Common Stock subject to such award having a value equal to the minimum amount required to be withheld under applicable federal, state and local income tax laws (collectively, “Withholding Taxes”). The value of shares of Common Stock to be withheld shall be based on the closing price of such shares on the date the amount of Withholding Taxes is determined.

4

2.             Definitions.

(a)           “Cause” shall mean:

(i)            The Executive is convicted of a felony or any crime involving moral turpitude; or

(ii)           A reasonable determination by directors comprising two-thirds of the entire Board of Directors of the Company (the “Board”), after giving the Executive notice and an opportunity to be heard, that (A) the Executive has willfully and continuously failed to perform substantially his duties as contemplated by Section 2 of the Employment Agreement (other than such failure resulting from incapacity due to physical or mental illness), after a written demand for corrected performance is delivered to the Executive by the Board which specifically identifies the manners in which the Board believes the Executive has not substantially performed his duties or (B) the Executive has engaged in gross neglect or gross misconduct, resulting in material harm to the Company.

(b)           “Constructive Discharge” shall mean the occurrence of any of the following circumstances:

(i)            A reduction by the Company in the Executive’s “Base Salary” or “Annual Bonus target” (as defined in the Employment Agreement) to an amount that is less than required under Section 4 of the Employment Agreement or the Company’s failure to provide the other elements of compensation set forth in Section 4 of the Employment Agreement;

(ii)           The removal of the Executive from the position of Chairman and Chief Executive Officer or the failure of the Executive to be nominated or reelected to the Company’s Board of Directors;

(iii)          Any action by the Company which results in significant diminution in the Executive’s authority, power, responsibilities or duties from those contemplated by Sections 1 and 2 of the Employment Agreement, or the assignment to the Executive without his written consent of any duties inconsistent with the Executive’s position and status as Chairman and Chief Executive Officer of the Company as contemplated by Sections 1 and 2 of the Employment Agreement, which action or assignment continues after written notice thereof and a reasonable opportunity to cure of not less than fifteen (15) days has been given by the Executive to the Company;

(iv)          The failure of the Company to obtain a satisfactory agreement from any successor, assignee, or transferee to expressly assume the liabilities, obligations and duties of the Company hereunder in accordance with the requirements of Section 13 of the Employment Agreement, unless such liabilities, obligations and duties of the Company are automatically assumed by any such successor, assignee or transferee by operation of law; or

(v)           Any other breach by the Company of any of its material obligations to the Executive under the Employment Agreement or this Agreement, which

5

breach continues after written notice thereof and a reasonable opportunity to cure of not less than thirty (30) days has been given by the Executive to the Company.

(c)           “Disability” means that the Executive is disabled within the meaning of the Company’s long–term disability policy or, if there is no such policy in effect, that (i) the Executive has been substantially unable, for 120 business days within a period of 180 consecutive business days, to perform the Executive’s duties under the Employment Agreement, as a result of physical or mental illness or injury, and (ii) a physician selected by the Company or its insurers, and reasonably acceptable to the Executive or the Executive’s legal representative, has determined that the Executive is disabled. A termination of the Executive’s employment by the Company for Disability shall be communicated to the Executive by written notice, and shall be effective on the 30th day after receipt of such notice by the Executive (the “Disability Effective Time”), unless the Executive returns to full-time performance of the Executive’s duties before the Disability Effective Time.

(d)           “Incumbent Board” shall have the meaning given to such term in subparagraph 6(d)(vi)(B) of the Employment Agreement.

3.             Assignability, Binding Nature. Except as otherwise provided in this Section, this Agreement shall be binding upon and inure to the benefit of the parties and their respective successors, heirs (in the case of the Executive) and assigns. No rights or obligations of the Company under this Agreement may be assigned or transferred by the Company except that such rights or obligations may be assigned or transferred pursuant to a merger or consolidation in which the Company is not the continuing entity, or the sale or liquidation of all or substantially all of the assets of the Company, provided that the assignee or transferee is the successor to all or substantially all of the assets of the Company and such assignee or transferee assumes the liabilities, obligations and duties of the Company, as contained in this Agreement, either contractually or a matter of law. The Company further agrees that, in the event of a merger or consolidation in which the Company is not the continuing entity or a sale of assets or liquidation as described in the preceding sentence, it shall take whatever action it legally can in order to cause the successor, assignee or transferee to expressly assume the liabilities, obligations and duties of the Company hereunder. No rights or obligations of the Executive under this Agreement may be assigned or transferred by the Executive other than his rights with respect to options that may be transferred in accordance with subparagraph 1(i) of this Agreement.

4.             Amendment. This Agreement may be amended or canceled only by mutual agreement of the parties in writing without the consent of any other person. So long as the Executive lives, no person, other than the parties hereto, shall have any rights under or interest in this Agreement or the subject matter hereto except that in the event of the Executive’s Disability so as to render him incapable of such action, his legal representative may be substituted for purposes of such amendment.

5.             Applicable Law. The provisions of this Agreement shall be construed in accordance with the internal laws of the State of Colorado, without regard to the conflict of law provisions of any state.

6

6.             Severability. The invalidity or unenforceability of any provision of this Agreement will not affect the validity or enforceability of any other provision of this Agreement, and this Agreement will be construed as if such invalid or unenforceable provision were omitted (but only to the extent such provision cannot be appropriately reformed or modified).

7.             Waiver of Breach. No waiver by any party hereto of a breach of any provision of this Agreement by any other party, or of compliance with any condition or provision of this Agreement to be performed by such other party, will operate or be construed as a waiver of any subsequent breach by such other party or any similar or dissimilar provisions and conditions at the same or any prior or subsequent time. The failure of any party hereto to take any action by reason of such breach will not deprive such party of the right to take action at any time while such breach continues.

8.             Notices. Notices and all other communications provided for in this Agreement shall be in writing and shall be delivered personally or sent by registered or certified mail, return receipt requested, postage prepaid, or sent by facsimile, or prepaid overnight courier to the parties at the facsimile phone numbers or addresses set forth below (or such other addresses or facsimile numbers as shall be specified by the parties by like notice):

Each party, by written notice furnished to the other party, may modify the applicable delivery address, except that notice of change of address shall be effective only upon receipt. Such notices, demands, claims and other communications shall be deemed given in the case of delivery by overnight service with guaranteed next day delivery, the next day or the day designated for delivery; or in the case of certified or registered U.S. mail, five days after deposit

7

in the U.S. mail; or, in the case of facsimile, the date upon which the transmitting party received confirmation of receipt by facsimile, telephone, or otherwise; provided, however, that in no event shall any such communications be deemed to be given later than the date they are actually received.

9.             Arbitration of Disputes and Reimbursement of Legal Costs. Any controversy or claim arising out of or relating to this Agreement (or the breach thereof) shall be settled by final, binding and non-appealable arbitration in Denver, Colorado. Company and Executive shall use good faith efforts to agree upon a single arbitrator. If Company and Executive are unable to agree upon a single arbitrator, the arbitration shall be conducted by three arbitrators. Subject to the following provisions, the arbitration shall be conducted in accordance with the rules of the American Arbitration Association (the “Association”) then in effect. If three arbitrators are used, one of the arbitrators shall be appointed by the Company, one shall be appointed by the Executive and the third shall be appointed by the first two arbitrators. If the first two arbitrators cannot agree on the third arbitrator within 30 days of the appointment of the second arbitrator, then the third arbitrator shall be appointed by the Association and shall be experienced in the resolution of disputes under employment agreements for CEOs of major corporations. Any award entered by the arbitrators shall be final, binding and non-appealable and judgment may be entered thereon by either party in accordance with applicable law in any court of competent jurisdiction. This arbitration provision shall be specifically enforceable. The arbitrators shall have no authority to modify any provision of this Agreement except as necessary to construe, reform or modify this Agreement to resolve a provision which is invalid or unenforceable. Other than as set forth herein, the arbitrators shall have no authority to add to, detract from, change, amend or modify existing law, or to award a remedy for a dispute involving this Agreement other than a benefit specifically provided under or by virtue of the Agreement, unless required by law. If the Executive prevails on any material issue which is the subject of such arbitration or lawsuit, the Company shall be responsible for all of the fees of the American Arbitration Association and the arbitrators and any expenses relating to the conduct of the arbitration (including the Company’s and the Executive’s reasonable attorneys’ fees and expenses), which fees and expenses shall be paid no later than the fifteenth day of the third month of the calendar year following the calendar year in which the arbitrators render a final decision. Otherwise, each party shall be responsible for its own expenses relating to the conduct of the arbitration (including reasonable attorneys’ fees and expenses) and shall share the fees of the American Arbitration Association equally.

10.           Survivorship. Upon the expiration or other termination of this Agreement, the respective rights and obligations of the parties hereto shall survive such expiration or other termination to the extent necessary to carry out the intentions of the parties under this Agreement.

11.           Entire Agreement. Except as otherwise noted herein, this Agreement and Section 8 of the Employment Agreement constitute the entire agreement between the parties concerning the subject matter hereof and supersedes all prior and contemporaneous agreements, if any, between the parties relating to the subject matter hereof.

8

12.           Counterparts. This Agreement may be executed in separate counterparts, each of which is deemed to be an original an all of which taken together constitute one and the same agreement.

IN WITNESS WHEREOF, the Executive has hereunto set his hand, and the Company has caused this Agreement to be executed in its name and on its behalf, all on the day and year first above written.

9