1 EXHIBIT 99.4 PAYLESS SHOESOURCE, INC. DEFERRED COMPENSATION PLAN (as amended April 20, 1998) SECTION 1. PURPOSE. The purpose of this Plan is to provide an additional incentive to the key employees of Payless ShoeSource, Inc. to achieve superior performance. SECTION 2. DEFINITIONS. (a) Board means the Board of Directors of Payless, as hereinafter defined. (b) Committee means the Committee appointed to administer the Plan, as hereinafter defined, as provided in Section 8 hereof. (c) Common Stock means the Common Stock of Payless, as hereinafter defined. (d) Corporation means Payless, as hereinafter defined, or any subsidiary of Payless which is an employer of an Executive, as hereinafter defined, who is a Participant, as hereinafter defined, in the Plan, as hereinafter defined. (e) Executive means any individual employed by the Corporation in an executive capacity who receives regular stated compensation in respect of such employer-employee relationship other than a pension, retainer or fee under a contract. (f) Fiscal Year means the fiscal year of the Corporation as established from time to time. (g) Payless means Payless ShoeSource, Inc., a Missouri corporation, provided, that immediately after the effective time of Merger such term shall mean Payless ShoeSource, Inc.(formerly Payless ShoeSource Holdings, Inc.) , a Delaware corporation, its successors and assigns. (h) Participant means an Executive who has been designated by the Committee as eligible, and who has elected to participate in the Plan, as hereinafter defined. (i) Plan means the Deferred Compensation Plan of the Corporation, as described herein. 2 (j) Stock Unit means an accounting equivalent of one share of Common Stock. (k) Stock Unit Account means an account on the records of the Corporation in respect of Stock Units which have been and/or may be allocated to a Participant in the manner hereinafter set forth. (l) "Merger" means the merger of Payless Merger Corp., a Missouri corporation and wholly-owned subsidiary of Payless ShoeSource, Inc. (formerly Payless ShoeSource Holdings, Inc.), a Delaware corporation, with the Corporation, pursuant to an Agreement and Plan of Merger among the Corporation, Payless Merger Corp. and Payless ShoeSource, Inc. (formerly Payless ShoeSource Holdings, Inc.). SECTION 3. METHODS OF PAYMENT. (a) Except as hereinafter provided, prior to the commencement of the calendar year that includes the first day of a Fiscal Year, each Participant shall be afforded the opportunity of making an election to have any one or more of the following alternative methods of payment applied to all or a part of any portion (which such portion shall not exceed one-half, unless specifically provided for to the contrary in the participant's written contract of employment) of any compensation of which such Participant shall be the recipient in respect of his performance during such Fiscal Year: (i) Alternative (i): Payment of any such compensation that is paid in the form of a bonus on the first day of April next following the close of such Fiscal Year or on such subsequent date as the amount thereof is ascertainable. (ii) Alternative (ii): Payment thereof at a deferred date or dates either in a lump sum or in annual installments, as may be determined by the Committee, such payment when made to include interest, as hereinafter provided, from the first day of April next following the Fiscal Year in respect of which the compensation was payable to the date of payment. (iii) Alternative (iii): Payment thereof at a deferred date or dates either in a lump sum or in annual installments, as may be determined by the Committee, and either in cash or in Common Stock or in both cash and Common Stock, as may be determined by the Committee, in respect of Stock Units to be allocated to the Participant as hereinafter provided. If any Participant shall fail to make an election with respect to any year, he shall be deemed to have elected not to defer any portion of his compensation for such year. Notwithstanding the requirements imposed by this paragraph (a) with respect to the time by which an election must be made, an employee who is designated by the 2 3 Committee as a Participant for the first time may, within 60 days of such designation, make any election otherwise permitted under this paragraph (a) with respect to the Participant's compensation in respect of employment subsequent to the date on which the election is made. (b) In connection with all determinations to be made by the Committee as respects Alternative (ii) and, except for the determination of whether payment thereunder is to be made in cash or in Common Stock or in both cash and Common Stock (which determination shall be in the absolute discretion to the Committee), Alternative (iii), the Participant shall be given an opportunity at the time he makes his election of indicating his preferences, which preferences shall be taken into account by the Committee in making its determinations. Except as provided in Section 12 and Section 13 in no event shall payments under Alternative (ii) or (iii) commence prior to the earliest of the Participant's retirement, termination of employment or death (or prior to the occurrence of a severe financial hardship, as provided below). The Committee shall make its determination with respect to the payment schedule (i.e., a lump sum payment or payments in annual installments) under Alternative (ii) or (iii) prior to the commencement of the calendar year that includes the first day of the Fiscal Year for which such alternative is elected. Except in the event of a severe financial hardship, as provided below, the Committee's determination with respect to a payment schedule shall become irrevocable as of the first day of the calendar year that includes the first day of the Fiscal Year for which the determination is made. However, upon the written request of the Participant (or if applicable, the beneficiary or distributee) the payment schedule may be revised by the Committee, in its absolute discretion, in the event that the Participant (or if applicable, the beneficiary or distributee) incurs a severe financial hardship. Such severe financial hardship must have been caused by an accident, illness or other event which was beyond the control of the Participant (or, if applicable, the beneficiary or distributee); and the Committee shall revise the payment schedule that it had previously established only to the extent that the Committee considers necessary to eliminate the severe financial hardship. Notwithstanding the requirements imposed by this paragraph (b) regarding the date by which the Committee must make a determination with respect to the payment schedule under Alternative (ii) or (iii) and the date as of which such determination shall become irrevocable (except in the event of a severe financial hardship), when a Participant makes an election pursuant to the last sentence of paragraph (a) of this Section 3, the Committee shall make its determination with respect to the payment schedule at any time prior to the date as of which the Participant's election becomes effective, and its determination shall become irrevocable (except in the event of a severe financial hardship) as of such effective date. (c) In the case of a Participant who elects to have all or any part of his compensation for a particular Fiscal Year paid under Alternative (iii), Stock Units shall be allocated to such Participant by crediting the same to his Stock Unit Account, and 3 4 the number of Stock Units to be so credited for such Fiscal Year shall be the sum of the following: (i) the quotient, disregarding fractions, resulting from dividing the dollar amount of such portion of the Participant's compensation as is to be so applied to Alternative (iii) by the average closing price of the Common Stock on the New York Stock Exchange during the month of February ending in the Fiscal Year next following the Fiscal Year in respect of which such compensation was payable; plus (ii) the quotient, disregarding fractions, resulting from dividing the aggregate dollar amount of cash dividends which would have been paid to the Participant during such Fiscal Year had the Stock Units standing in his Stock Unit Account from time to time during such Fiscal Year been shares of Common Stock by the average dosing price of the Common Stock on the New York Stock Exchange during the month of February ending in the year next following such Fiscal Year; plus (iii) the number of shares of Common Stock, disregarding fractions, which would have been received by the Participant as stock dividends during such Fiscal Year had the Stock Units standing in his Stock Unit Account at the date or dates of payment of such stock dividend(s) been shares of Common Stock. Any allocation of Stock Units to a Participant's Stock Unit Account required to be made pursuant to this paragraph (c) shall be made as of the first day of April next following the Fiscal Year in respect of which such compensation was payable or such dividends were paid, as the case may be. The aggregate value of the fraction or fractions remaining after making the applicable calculations referred to in subparagraphs (c)(i), (c)(ii) and (c)(iii) of this Section 3 (based upon the average closing price of Common Stock on the New York Stock Exchange during the month of February next preceding such month of April), shall not be converted into Stock Units but shall be allocated and added to the amount elected by the Participant to be paid to him under Alternative (ii) above, or, if the Participant shall have made no such election under Alternative (ii), then such remaining amount shall be paid to the Participant as if he had made an election under Alternative (i) above to be so paid. (d) Notwithstanding the provisions of Section 3(c) to the contrary, in the event of a recapitalization of Payless pursuant to which the outstanding shares of Common Stock shall be changed into a greater or smaller number of shares (including, without limitation, a stock split or a stock dividend of 25% or more of the number of outstanding shares of Common Stock), the number of Stock Units credited to a Participant's Stock Unit Account shall be appropriately adjusted as of the effective date of such recapitalization. 4 5 (e) Interest to be paid under Alternative (ii) shall be credited annually as of April 1 of each year and shall be at a rate shall be equal to the average yield on long-term United States Government Bonds (as determined by the Board of Governors of the Federal Reserve Board and published in the Federal Reserve Bulletin) for the calendar year prior to said April 1, compounded annually, provided, however, that if the method of calculation of such average yield shall be changed, or if the determination and/or the publication thereof be discontinued, then the Committee shall substitute therefor such alternative method of determining such interest rate as it, in its discretion, shall deem appropriate. (f) [In effect with respect to elections made with respect to the 1999 Fiscal Year and deleted thereafter.] At the same time and in the same manner as a Participant may elect an alternative method of payment under Section 3(a), any such Participant who has previously elected Alternative (ii) or (iii) for a prior Fiscal Year may indicate his preference to have all or a portion of his Cash Units reallocated and credited to his Stock Unit Account, or all or a portion of his Stock Unit Account reallocated and credited to Cash Units. Any reallocation from a Participant's Cash Units (to be invested in his Stock Unit Account) shall be based on the value of the Participant's Cash Units as of the April 1 following the Participant's election, and any crediting of a Participant's Cash Units (by reason of a reallocation from his Stock Unit Account) will be credited as of April 1. Any reallocation from a Participant's Stock Unit Account (to be invested in Cash Units) and any crediting of a Participant's Stock Unit Account (by reason of a reallocation from his Cash Units) will be based on the value of Stock Units determined under paragraph (c) (i) and, if applicable, (c) (ii) and (iii) above, and such reallocation shall occur as of the April 1 following the Participant's election. The Committee's determination as to whether or not to honor a Participant's preference to reallocate Cash Units to Stock Units shall be subject to the limitation of Section 4. SECTION 4. LIMITATION OF STOCK UNITS. In no event shall the aggregate number of Stock Units allocated under this Plan in respect of compensation for any Fiscal Year exceed a number equal to 1/2 of 1% of the total number of shares of Common Stock outstanding at the close of such Fiscal Year. SECTION 5. DISTRIBUTION FROM THE STOCK UNIT ACCOUNT. (a) Distribution from a Participant's Stock Unit Account shall be made in accordance with the determinations made by the Committee, as provided in this Plan. Stock Units shall be adjusted from time to time in accordance with this Plan until all distributions to which a Participant is entitled hereunder shall have been made. 5 6 (b) If the Committee determines that distribution to a Participant is to be made in annual installments, the Committee may determine from time to time whether each particular installment shall be distributed in cash or in Common Stock or in both cash and Common Stock. (c) If the Committee determines that a distribution to a Participant is to be made in a lump sum in Common Stock, the number of shares of Common Stock to be so distributed to such Participant shall equal the number of Stock Units then in his Stock Unit Account. For the purpose of determining the number of shares of Common Stock to be distributed on a particular annual installment distribution date, the Committee shall make its calculations as if that annual installment and all subsequent annual installments were in fact to be made in shares of Common Stock, as follows: the number of shares of Common Stock which would be then so distributable, except in the case of the last distribution, shall be equal to the product, disregarding fractions, of the total number of Stock Units then credited to the Participant's Stock Unit Account, multiplied by a fraction, the numerator of which shall be one and the denominator of which shall be the number of remaining installments; and in the case of the last distribution, shall be the number of shares of Common Stock equal to the Stock Units then remaining in the Participant's Stock Unit Account. The Participant's Stock Unit Account shall be decreased by one Stock Unit for each share of Common Stock distributed to a Participant. (d) If the Committee determines that a particular distribution to a Participant is to be made in cash, a computation shall first be made of the number of shares of Common Stock which would then be distributable pursuant to paragraph (c) of this Section 5 if such distribution were to be made in shares of Common Stock. The number of shares thus determined shall then be converted into cash in respect of each such distribution by valuing such shares at the average dosing price of the Common Stock on the New York Stock Exchange during the month of February next preceding the date of such distribution, and the resulting amount of cash shall be distributed to the Participant. The Participant's Stock Unit Account shall then be decreased by one Stock Unit for each share of Common Stock which would have been distributed to the Participant had such cash distribution been made in shares of Common Stock. (e) If the Committee determines that a distribution is to be made in part in Common Stock and in part in cash, paragraphs (c) and (d) of this Section 5 shall be applied separately to the respective parts of such distribution and to the respective parts of the Stock Unit Account with respect to which the distribution is to be made. 6 7 SECTION 6. DEATH OF PARTICIPANT. In the event of the death of a Participant prior to complete distribution under Alternatives (ii) and/or (iii) hereof, all cash and/or Stock Units then remaining undistributed, or which shall thereafter become distributable to him pursuant to such Alternatives, shall be distributed to such beneficiary as the Participant shall have designated in writing to the Corporation, or, in the absence of such designation, to his personal representative. Such distribution shall be made at such date or dates either in a lump sum or in annual installments, as may be determined by the Committee prior to the beginning of the calendar year that includes the first day of the Fiscal Year for which such alternative is elected (or, where applicable, the date specified by the last sentence of Section 3(b)); provided, however, that in the event of a severe financial hardship, the Committee may subsequently revise its determination in accordance with the applicable provisions of Section 3(b). SECTION 7. PARTICIPANT'S RIGHT UNSECURED; INVESTMENTS. The right of a Participant to receive any distribution hereunder shall be an unsecured claim against the general assets of the Corporation. Nothing in this Agreement shall require the Corporation to invest any amount, the payment of which has been deferred under Alternative (ii) or (iii), in Common Stock or in any other medium. SECTION 8. ADMINISTRATION OF THE PLAN COMMITTEE. (a) The Plan shall be administered by a Committee of not less than two nor more than five persons designated by the Board (which may, but need not, be the compensation committee of the Board), all of whom shall be directors of the Corporation and shall serve at the pleasure of the Board. In no event shall any member of the Committee be a Participant. The Committee shall act by vote or written consent of a majority of its members (except in the case of a two person Committee in which case any vote or written consent must be unanimous). The Plan may be amended, modified or terminated by the Board, except that no change may be made without the approval of the Common Shareowners of Payless (i) the maximum number of shares or Stock Units deliverable or allocable in respect of any Fiscal Year under the plan or (ii) in the provisions of subparagraphs (c)(i) and (c)(ii) of Section 3 of this Plan relating to the method of determining the number of Stock Units allocable to a Participant. (b) The Committee shall prescribe such forms as it considers appropriate for the administration of the Plan. The forms shall set forth such terms and conditions not inconsistent with the terms of the Plan as the Committee may determine and shall designate: 7 8 (i) the alternative or alternatives elected by the Participant pursuant to Section 3(a); (ii) the Committee's determination of the time or times when payment of such compensation will be made to the Participant pursuant to Section 3(b)(in the absence of a severe financial hardship); (iii) the beneficiary (if any) designated by the Participant pursuant to Section 6; and (iv) the Committee's determination of the time or times when payment of such compensation will be made after the Participant's death pursuant to Section 6 (in the absence of a severe financial hardship). SECTION 9. SUCCESSORS. The provisions of the Plan with respect to each Participant shall bind the legatees, heirs, executors, administrators or other successors in interest of such Participant. SECTION 10. ALIENATION. (a) Subject to the provisions of Section 6 and paragraph (b) of this Section 10, no amount, the payment of which as been deferred under Alternative (ii) or (iii), shall be subject in any manner to anticipation, alienation, sale, transfer, assignment, pledge, encumbrance, levy or charge, and any attempt to so anticipate, alienate, sell, transfer, assign, pledge, encumber, levy or charge the same shall be void; nor shall any such amount be in any manner liable for or subject to the debts, contracts, liabilities, engagements or torts of the person entitled to such benefit. (b) Nothing in this Section 10 shall prohibit the personal representative of a Participant from designating that any amount be distributed in accordance with the terms of the Participant's will or pursuant to the laws of descent and distribution. SECTION 11. WITHHOLDING. There shall be deducted from all amounts paid under this Plan any taxes required to be withheld by any federal, state or local government. The Participants and their beneficiaries, distributees and personal representatives will bear any and all federal, foreign, state, local or other income or other taxes imposed on amounts paid under this Plan as to which no amounts are withheld, irrespective of whether withholding is required. 8 9 SECTION 12. DISCRETIONARY PAYMENT. (a) Notwithstanding any other provision in any other Section of the Plan to be contrary, the Committee may, in its sole and absolute discretion, direct an immediate payment of cash and/or distribution of Stock with respect to amounts (except those referred to in the next proviso) previously deferred under this Plan if the Committee determines that such action is in the best interests of Payless, the Participants and their beneficiaries. (b) In the event that the Committee shall so direct an immediate payment, distribution and/or release in accordance with Section 12(a), then (i) the amounts of cash and the numbers of shares of Stock to be so paid and/or distributed shall be determined by the Committee so as to reflect fairly and equitably appropriate interest and dividends since the preceding April 1 and so as to reflect fairly and equitably such other facts and circumstances as the Committee deems appropriate, including, without limitation, recent price of the Stock; (ii) amounts which were otherwise deferred or to be deferred with respect to the Fiscal Year or long-term period in which such payment or distribution occurs shall be paid when otherwise payable (such amounts which would otherwise have been payable prior to the date of such payment or distribution shall be paid as soon as practicable thereafter); (iii) in the event that cash is not paid or made available to a Participant when otherwise due or that shares of Stock are not distributed or otherwise made available to a Participant when otherwise due, then such Participant may file a claim for such payment or distribution and, if such Participant is successful, then the Corporation shall reimburse such Participant for reasonable attorneys' fees actually paid by the Participant in enforcing such Participant's rights to such payment or distribution; and (iv) in the event that cash is not paid or made available to a Participant when otherwise due, then interest will accrue with respect to such unpaid amount from the date it was otherwise due until the date it is actually paid at a rate equal to two percentage points over the prime rate as in effect from time to time, as determined in good faith the Committee based on the prime rate charged from time to time by major banks in the City of New York. 9 10 SECTION 13. CHANGE IN CONTROL. Notwithstanding any other provision in any other Section of this Plan to the contrary, (i) the value of all amounts deferred by a Participant which have not yet been credited to the Participant's accounts under this Plan and (u) the value of all of a Participant's accounts under this Plan shall be paid to such Participant in each case in a lump sum cash payment on the occurrence of a Change in Control of the Corporation or as soon thereafter as practicable, but in no event later than five days after the Change in Control of the Corporation. The amounts of cash credited to each Participant's accounts prior to determining the amount of cash to be paid from these accounts shall be determined by the Committee (which, for this purpose, shall be comprised of members of the Board prior to the Change in Control of the Corporation) so as to reflect fairly and equitably appropriate interest and dividends since the preceding April 1 and so as to reflect fairly and equitably such other facts and circumstances as the Committee deems appropriate, including, without limitation, recent price of the stock. For purposes of payments under this Section 13, the value of Stock Unit shall be computed as the greater of (a) the closing price of shares of Common Stock as reported on the New York Stock Exchange on or nearest the date on which the Change in Control is deemed to occur (or, if not listed on such exchange, on a nationally recognized exchange or quotation system on which trading volume in the Common Stock is highest) or (b) the highest per share price for shares of Common Stock actually paid in connection with any Change in Control. For purposes of this Plan, a "Change in Control of the Corporation" shall be deemed to have occurred if (a) any "person" as such term is used in Section 13(d) and 14(d) of the Securities Exchange Act of 1934, as amended (the "Exchange Act") (other than the Corporation, any trustee or other fiduciary holding securities under an employee benefit plan of the Corporation, or any company owned, directly or indirectly, by the shareowners of the Corporation in substantially the same proportions as their ownership of stock of the Corporation), is or becomes the "beneficial owner. (as defined in Rule 13d-3 under Exchange Act), directly or indirectly of securities of the Corporation representing 50% or more of the combined voting power of the Corporation's then outstanding securities; (b) during any period of two consecutive years, individuals who at the beginning of such period constitute the Board, and any new director (other than a director designated by a person who has entered into an agreement with the Corporation to effect a transaction described in clause (a), (c) or (d) of this Section) whose election by the Board or nomination for election by the Corporation's shareowners was approved by a vote of at least two-thirds (2/3) of the directors then still in office who either were directors at the beginning of the period or whose election 10 11 or nomination for election was previously so approved cease for any reason to constitute at least a majority thereof; (c) the shareowners of the Corporation approve a merger or consolidation of the Corporation with any other Corporation, other than (1) a merger or consolidation which would result in the voting securities of the Corporation outstanding immediately prior thereto continuing to represent (either by remaining outstanding or by being converted into voting securities of the surviving entity) more than 50% of the combined voting power of the voting securities of the Corporation or such surviving entity outstanding immediately after such merger or consolidation or (2) a merger or consolidation effected to implement a recapitalization of the Corporation (or similar transaction) in which no "person" (as hereinabove defined) acquires more than 50% of the combined voting power of the Corporation's then outstanding securities; or (d) the shareowners of the Corporation approve a plan of complete liquidation of the Corporation or an agreement for the sale or disposition by the Corporation of all or substantially all of the Corporation's assets. 11