<PAGE>   1
                                                                    EXHIBIT 10.4




                           ARBOR SOFTWARE CORPORATION
                          EMPLOYEE STOCK PURCHASE PLAN


         I.       PURPOSE OF THE PLAN

                  This Employee Stock Purchase Plan is intended to promote the
interests of Arbor Software Corporation by providing eligible employees with the
opportunity to acquire a proprietary interest in the Corporation through
participation in a payroll-deduction based employee stock purchase plan designed
to qualify under Section 423 of the Code.

                  Capitalized terms herein shall have the meanings assigned to
such terms in the attached Appendix.

         II.      ADMINISTRATION OF THE PLAN

                  The Plan Administrator shall have full authority to interpret
and construe any provision of the Plan and to adopt such rules and regulations
for administering the Plan as it may deem necessary in order to comply with the
requirements of Code Section 423. Decisions of the Plan Administrator shall be
final and binding on all parties having an interest in the Plan.

         III.     STOCK SUBJECT TO PLAN

                 A. The stock purchasable under the Plan shall be shares of
authorized but unissued or reacquired Common Stock, including shares of Common
Stock purchased on the open market. The maximum number of shares of Common Stock
which may be issued over the term of the Plan shall not exceed Three Hundred
Fifty Thousand (350,000) shares.

                 B. Should any change be made to the Common Stock by reason of
any stock split, stock dividend, recapitalization, combination of shares,
exchange of shares or other change affecting the outstanding Common Stock as a
class without the Corporation's receipt of consideration, appropriate
adjustments shall be made to (i) the maximum number and class of securities
issuable under the Plan, (ii) the maximum number and class of securities
purchasable per Participant on any one Purchase Date and (iii) the number and
class of securities and the price per share in effect under each outstanding
purchase right in order to prevent the dilution or enlargement of benefits
thereunder.

         IV.      OFFERING PERIODS

                  A. Shares of Common Stock shall be offered for purchase under
the Plan through a series of successive offering periods until such time as (i)
the maximum number of shares of Common Stock available for issuance under the
Plan shall have been purchased or (ii) the Plan shall have been sooner
terminated.




                                       1
<PAGE>   2
                  B. Each offering period shall be of such duration (not to
exceed twenty-four (24) months) as determined by the Plan Administrator prior to
the start date. The initial offering period shall commence at the Effective Time
and terminate on the last business day in October 1997. The next offering period
shall commence on the first business day in November 1997, and subsequent
offering periods shall commence as designated by the Plan Administrator.

                  C. Each offering period shall be comprised of a series of one
or more successive Purchase Periods. Purchase Periods shall begin on the first
business day in May and November each year and terminate on the last business
day in the following April and October, respectively, each year. However, the
first Purchase Period under the initial offering period shall commence at the
Effective Time and terminate on the last business day in April 1996.

         V.       ELIGIBILITY

                  A. Each Eligible Employee shall be eligible to enter an
offering period under the Plan on the start date of any Purchase Period within
that offering period, provided he or she remains an Eligible Employee on such
start date. The date such individual enters the offering period shall be
designated his or her Entry Date for purposes of that offering period.

                  B. To participate in the Plan for a particular offering
period, the Eligible Employee must complete the enrollment forms prescribed by
the Plan Administrator (including a stock purchase agreement and a payroll
deduction authorization form) and file such forms with the Plan Administrator
(or its designate) on or before his or her scheduled Entry Date.

         VI.       PAYROLL DEDUCTIONS

                  A. The payroll deduction authorized by the Participant for
purposes of acquiring shares of Common Stock under the Plan may be any multiple
of one percent (1%) of the Cash Compensation paid to the Participant during each
Purchase Period within that offering period, up to a maximum of ten percent
(10%). The deduction rate so authorized shall continue in effect for the
remainder of the offering period, except to the extent such rate is changed in
accordance with the following guidelines:

                                 (i) The Participant may, at any time during the
         offering period, reduce his or her rate of payroll deduction to become
         effective as soon as possible after filing the appropriate form with
         the Plan Administrator. The Participant may not, however, effect more
         than one (1) such reduction per Purchase Period.

                                 (ii) The Participant may, prior to the
         commencement of any new Purchase Period within the offering period,
         increase the rate of his or her payroll deduction by filing the
         appropriate form with the Plan Administrator. The new rate (which may
         not exceed the ten percent (10%) maximum) shall become effective as of
         the start date of the Purchase Period following the filing of such
         form.




                                       2
<PAGE>   3
                  B. Payroll deductions shall begin on the first pay day
following the Participant's Entry Date into the offering period and shall
(unless sooner terminated by the Participant) continue through the pay day
ending with or immediately prior to the last day of that offering period. The
amounts so collected shall be credited to the Participant's book account under
the Plan, but no interest shall be paid on the balance from time to time
outstanding in such account. The amounts collected from the Participant shall
not be held in any segregated account or trust fund and may be commingled with
the general assets of the Corporation and used for general corporate purposes.

                  C. Payroll deductions shall automatically cease upon the
termination of the Participant's purchase right in accordance with the
provisions of the Plan.

                  D. The Participant's acquisition of Common Stock under the
Plan on any Purchase Date shall neither limit nor require the Participant's
acquisition of Common Stock on any subsequent Purchase Date, whether within the
same or a different offering period.

         VII.     PURCHASE RIGHTS

                  A. Grant of Purchase Right. A Participant shall be granted a
separate purchase right for each offering period in which he or she
participates. The purchase right shall be granted on the Participant's Entry
Date into the offering period and shall provide the Participant with the right
to purchase shares of Common Stock, in a series of successive installments over
the remainder of such offering period, upon the terms set forth below. The
Participant shall execute a stock purchase agreement embodying such terms and
such other provisions (not inconsistent with the Plan) as the Plan Administrator
may deem advisable.

                  Under no circumstances shall purchase rights be granted under
the Plan to any Eligible Employee if such individual would, immediately after
the grant, own (within the meaning of Code Section 424(d)) or hold outstanding
options or other rights to purchase, stock possessing five percent (5%) or more
of the total combined voting power or value of all classes of stock of the
Corporation or any Corporate Affiliate.

                  B. Exercise of the Purchase Right. Each purchase right shall
be automatically exercised in installments on each successive Purchase Date
within the offering period, and shares of Common Stock shall accordingly be
purchased on behalf of each Participant (other than any Participant whose
payroll deductions have previously been refunded in accordance with the
Termination of Purchase Right provisions below) on each such Purchase Date. The
purchase shall be effected by applying the Participant's payroll deductions for
the Purchase Period ending on such Purchase Date (together with any carryover
deductions from the preceding Purchase Period) to the purchase of whole shares
of Common Stock (subject to the limitation on the maximum number of shares
purchasable per Participant on any one Purchase Date) at the purchase price in
effect for the Participant for that Purchase Date.

                  C. Purchase Price. The purchase price per share at which
Common Stock will be purchased on the Participant's behalf on each Purchase Date
within the offering period shall be






                                       3
<PAGE>   4
equal to eighty-five percent (85%) of the lower of (i) the Fair Market Value per
share of Common Stock on the Participant's Entry Date into that offering period
or (ii) the Fair Market Value per share of Common Stock on that Purchase Date.
However, for each Participant whose Entry Date is other than the start date of
the offering period, the clause (i) amount shall in no event be less than the
Fair Market Value per share of Common Stock on the start date of that offering
period.

                  D. Number of Purchasable Shares. The number of shares of
Common Stock purchasable by a Participant on each Purchase Date during the
offering period shall be the number of whole shares obtained by dividing the
amount collected from the Participant through payroll deductions during the
Purchase Period ending with that Purchase Date (together with any carryover
deductions from the preceding Purchase Period) by the purchase price in effect
for the Participant for that Purchase Date. However, the maximum number of
shares of Common Stock purchasable per Participant on any one Purchase Date
shall not exceed Five Hundred (500) shares, subject to periodic adjustments in
the event of certain changes in the Corporation's capitalization.

                  E. Excess Payroll Deductions. Any payroll deductions not
applied to the purchase of shares of Common Stock on any Purchase Date because
they are not sufficient to purchase a whole share of Common Stock shall be held
for the purchase of Common Stock on the next Purchase Date. However, any payroll
deductions not applied to the purchase of Common Stock by reason of the
limitation on the maximum number of shares purchasable by the Participant on the
Purchase Date shall be promptly refunded.

                  F. Termination of Purchase Right. The following provisions
shall govern the termination of outstanding purchase rights:

                                 (i) A Participant may, at any time prior to the
         next Purchase Date in the offering period, terminate his or her
         outstanding purchase right by filing the appropriate form with the Plan
         Administrator (or its designate), and no further payroll deductions
         shall be collected from the Participant with respect to the terminated
         purchase right. Any payroll deductions collected during the Purchase
         Period in which such termination occurs shall, at the Participant's
         election, be immediately refunded or held for the purchase of shares on
         the next Purchase Date. If no such election is made at the time such
         purchase right is terminated, then the payroll deductions collected
         with respect to the terminated right shall be refunded as soon as
         possible.

                                 (ii) The termination of such purchase right
         shall be irrevocable, and the Participant may not subsequently rejoin
         the offering period for which the terminated purchase right was
         granted. In order to resume participation in any subsequent offering
         period, such individual must re-enroll in the Plan (by making a timely
         filing of the prescribed enrollment forms) on or before his or her
         scheduled Entry Date into that offering period.





                                       4
<PAGE>   5
                                 (iii) Should the Participant cease to remain an
         Eligible Employee for any reason (including death, disability or change
         in status) while his or her purchase right remains outstanding, then
         that purchase right shall immediately terminate, and all of the
         Participant's payroll deductions for the Purchase Period in which the
         purchase right so terminates shall be immediately refunded. However,
         should the Participant cease to remain in active service by reason of
         an approved unpaid leave of absence, then the Participant shall have
         the election, exercisable up until the last business day of the
         Purchase Period in which such leave commences, to (a) withdraw all the
         funds in the Participant's payroll account at the time of the
         commencement of such leave or (b) have such funds held for the purchase
         of shares at the end of such Purchase Period. In no event, however,
         shall any further payroll deductions be added to the Participant's
         account during such leave. Upon the Participant's return to active
         service, his or her payroll deductions under the Plan shall
         automatically resume at the rate in effect at the time the leave began,
         provided the Participant returns to service prior to the expiration
         date of the offering period in which such leave began.

                  G. Corporate Transaction. Each outstanding purchase right
shall automatically be exercised, immediately prior to the effective date of any
Corporate Transaction, by applying the payroll deductions of each Participant
for the Purchase Period in which such Corporate Transaction occurs to the
purchase of whole shares of Common Stock at a purchase price per share equal to
eighty-five percent (85%) of the lower of (i) the Fair Market Value per share of
Common Stock on the Participant's Entry Date into the offering period in which
such Corporate Transaction occurs or (ii) the Fair Market Value per share of
Common Stock immediately prior to the effective date of such Corporate
Transaction. However, the applicable limitation on the number of shares of
Common Stock purchasable per Participant shall continue to apply to any such
purchase, and the clause (i) amount above shall not, for any Participant whose
Entry Date for the offering period is other than the start date of that offering
period, be less than the Fair Market Value per share of Common Stock on such
start date.

                  The Corporation shall use its best efforts to provide at least
ten (10)-days prior written notice of the occurrence of any Corporate
Transaction, and Participants shall, following the receipt of such notice, have
the right to terminate their outstanding purchase rights prior to the effective
date of the Corporate Transaction.

                  H. Proration of Purchase Rights. Should the total number of
shares of Common Stock which are to be purchased pursuant to outstanding
purchase rights on any particular date exceed the number of shares then
available for issuance under the Plan, the Plan Administrator shall make a
pro-rata allocation of the available shares on a uniform and nondiscriminatory
basis, and the payroll deductions of each Participant, to the extent in excess
of the aggregate purchase price payable for the Common Stock pro-rated to such
individual, shall be refunded.

                  I. Assignability. During the Participant's lifetime, the
purchase right shall be exercisable only by the Participant and shall not be
assignable or transferable by the Participant.




                                       5
<PAGE>   6
                  J. Stockholder Rights. A Participant shall have no stockholder
rights with respect to the shares subject to his or her outstanding purchase
right until the shares are purchased on the Participant's behalf in accordance
with the provisions of the Plan and the Participant has become a holder of
record of the purchased shares.

         VIII.    ACCRUAL LIMITATIONS

                  A. No Participant shall be entitled to accrue rights to
acquire Common Stock pursuant to any purchase right outstanding under this Plan
if and to the extent such accrual, when aggregated with (i) rights to purchase
Common Stock accrued under any other purchase right granted under this Plan and
(ii) similar rights accrued under other employee stock purchase plans (within
the meaning of Code Section 423) of the Corporation or any Corporate Affiliate,
would otherwise permit such Participant to purchase more than Twenty-Five
Thousand Dollars ($25,000) worth of stock of the Corporation or any Corporate
Affiliate (determined on the basis of the Fair Market Value of such stock on the
date or dates such rights are granted) for each calendar year such rights are at
any time outstanding.

                  B. For purposes of applying such accrual limitations, the
following provisions shall be in effect:

                                 (i) The right to acquire Common Stock under
         each outstanding purchase right shall accrue in a series of
         installments on each successive Purchase Date during the offering
         period on which such right remains outstanding.

                                 (ii) No right to acquire Common Stock under any
         outstanding purchase right shall accrue to the extent the Participant
         has already accrued in the same calendar year the right to acquire
         Common Stock under one (1) or more other purchase rights at a rate
         equal to Twenty-Five Thousand Dollars ($25,000) worth of Common Stock
         (determined on the basis of the Fair Market Value of such stock on the
         date or dates of grant) for each calendar year such rights were at any
         time outstanding.

                  C. If by reason of such accrual limitations, any purchase
right of a Participant does not accrue for a particular Purchase Period, then
the payroll deductions which the Participant made during that Purchase Period
with respect to such purchase right shall be promptly refunded.

                  D. In the event there is any conflict between the provisions
of this Article and one or more provisions of the Plan or any instrument issued
thereunder, the provisions of this Article shall be controlling.

         IX.      EFFECTIVE DATE AND TERM OF THE PLAN

                  A. The Plan was adopted by the Board on August 31, 1995 and
approved by the stockholders on September 15, 1995. The Plan shall become
effective at the Effective Time, provided no purchase rights granted under the
Plan shall be exercised, and no shares of Common





                                       6
<PAGE>   7
Stock shall be issued hereunder, until the Corporation shall have complied with
all applicable requirements of the 1933 Act (including the registration of the
shares of Common Stock issuable under the Plan on a Form S-8 registration
statement filed with the Securities and Exchange Commission), all applicable
listing requirements of any stock exchange (or the Nasdaq National Market, if
applicable) on which the Common Stock is listed for trading and all other
applicable requirements established by law or regulation.

                  B. Unless sooner terminated by the Board, the Plan shall
terminate upon the earliest of (i) the last business day in October 2005, (ii)
the date on which all shares available for issuance under the Plan shall have
been sold pursuant to purchase rights exercised under the Plan or (iii) the date
on which all purchase rights are exercised in connection with a Corporate
Transaction. No further purchase rights shall be granted or exercised, and no
further payroll deductions shall be collected, under the Plan following its
termination.

         X.       AMENDMENT OF THE PLAN

                  The Board may alter, amend, suspend or discontinue the Plan at
any time to become effective immediately following the close of any Purchase
Period. However, the Board may not, without the approval of the Corporation's
stockholders, (i) materially increase the number of shares of Common Stock
issuable under the Plan or the maximum number of shares purchasable per
Participant on any one Purchase Date, except for permissible adjustments in the
event of certain changes in the Corporation's capitalization, (ii) alter the
purchase price formula so as to reduce the purchase price payable for the shares
of Common Stock purchasable under the Plan, or (iii) materially increase the
benefits accruing to Participants under the Plan or materially modify the
requirements for eligibility to participate in the Plan.

         XI.      GENERAL PROVISIONS

                  A. All costs and expenses incurred in the administration of
the Plan shall be paid by the Corporation.

                  B. Nothing in the Plan shall confer upon the Participant any
right to continue in the employ of the Corporation or any Corporate Affiliate
for any period of specific duration or interfere with or otherwise restrict in
any way the rights of the Corporation (or any Corporate Affiliate employing such
person) or of the Participant, which rights are hereby expressly reserved by
each, to terminate such person's employment at any time for any reason, with or
without cause.

                  C. The provisions of the Plan shall be governed by the laws of
the State of California without resort to that State's conflict-of-laws rules.






                                       7
<PAGE>   8
                                   Schedule A

                          Corporations Participating in
                          Employee Stock Purchase Plan
                            As of the Effective Time

                           Arbor Software Corporation


<PAGE>   9
                                    APPENDIX


The following definitions shall be in effect under the Plan:

         A.       Board shall mean the Corporation's Board of Directors.

         B. Cash Compensation shall mean the (i) regular base salary paid to a
Participant by one or more Participating Companies during such individual's
period of participation in the Plan, plus (ii) any pre-tax contributions made by
the Participant to any Code Section 401(k) salary deferral plan or any Code
Section 125 cafeteria benefit program now or hereafter established by the
Corporation or any Corporate Affiliate, plus (iii) all of the following amounts
to the extent paid in cash: overtime payments, bonuses, commissions,
profit-sharing distributions and other incentive-type payments. However, Cash
Compensation shall not include any contributions (other than Code Section 401(k)
or Code Section 125 contributions) made on the Participant's behalf by the
Corporation or any Corporate Affiliate to any deferred compensation plan or
welfare benefit program now or hereafter established.

         C. Code shall mean the Internal Revenue Code of 1986, as amended.

         D. Common Stock shall mean the Corporation's common stock.

         E. Corporate Affiliate shall mean any parent or subsidiary corporation
of the Corporation (as determined in accordance with Code Section 424), whether
now existing or subsequently established.

         F. Corporate Transaction shall mean either of the following
stockholder- approved transactions to which the Corporation is a party:

                           (i) a merger or consolidation in which securities
         possessing more than fifty. percent (50%) of the total combined voting
         power of the Corporation's outstanding securities are transferred to a
         person or persons different from the persons holding those securities
         immediately prior to such transaction, or

                           (ii) the sale, transfer or other disposition of all
         or substantially all of the assets of the Corporation in complete
         liquidation or dissolution of the Corporation.

         G. Corporation shall mean Arbor Software Corporation, a Delaware
corporation, and any corporate successor to all or substantially all of the
assets or voting stock of Arbor Software Corporation which shall by appropriate
action adopt the Plan.








                                      A-1
<PAGE>   10
         H. Effective Time shall mean the time at which the Underwriting
Agreement is executed and finally priced. Any Corporate Affiliate which becomes
a Participating Corporation after such Effective Time shall designate a
subsequent Effective Time with respect to its employee-Participants.

         I. Eligible Employee shall mean any person who is engaged, on a
regularlyscheduled basis of more than twenty (20) hours per week for more than
five (5) months per calendar year, in the rendition of personal services to any
Participating Corporation as an employee for earnings considered wages under
Code Section 3401(a).

         J. Entry Date shall mean the date an Eligible Employee first commences
participation in the offering period in effect under the Plan. The earliest
Entry Date under the Plan shall be the Effective Time.

         K. Fair Market Value per share of Common Stock on any relevant date
shall be determined in accordance with the following provisions:

                           (i) If the Common Stock is at the time traded on the
         Nasdaq National Market, then the Fair Market Value shall be the closing
         selling price per share of Common Stock on the date in question, as
         such price is reported by the National Association of Securities
         Dealers on the Nasdaq National Market or any successor system. If there
         is no closing selling price for the Common Stock on the date in
         question, then the Fair Market Value shall be the closing selling price
         on the last preceding date for which such quotation exists.

                           (ii) If the Common Stock is at the time listed on any
         Stock Exchange, then the Fair Market Value shall be the closing selling
         price per share of Common Stock on the date in question on the Stock
         Exchange determined by the Plan Administrator to be the primary market
         for the Common Stock, as such price is officially quoted in the
         composite tape of transactions on such exchange. If there is no closing
         selling price for the Common Stock on the date in question, then the
         Fair Market Value shall be the closing selling price on the last
         preceding date for which such quotation exists.

                           (iii) For purposes of the initial offering period
         which begins at the Effective Time, the Fair Market Value shall be
         deemed to be equal to the price per share at which the Common Stock is
         sold in the initial public offering pursuant to the Underwriting
         Agreement.

         L. 1933 Act shall mean the Securities Act of 1933, as amended.

         M. Participant shall mean any Eligible Employee of a Participating
Corporation who is actively participating in the Plan.





                                      A-2
<PAGE>   11
         N. Participating Corporation shall mean the Corporation and such
Corporate Affiliate or Affiliates as may be authorized from time to time by the
Board to extend the benefits of the Plan to their Eligible Employees. The
Participating Corporations in the Plan as of the Effective Time are listed in
attached Schedule A.

         O. Plan shall mean the Corporation's Employee Stock Purchase Plan, as
set forth in this document.

         P. Plan Administrator shall mean the committee of two (2) or more Board
members appointed by the Board to administer the Plan.

         Q. Purchase Date shall mean the last business day of each Purchase
Period. The initial Purchase Date shall be April 30, 1996.

         R. Purchase Period shall mean each successive period within the
offering period at the end of which there shall be purchased shares of Common
Stock on behalf of each Participant.

         S. Stock Exchange shall mean either the American Stock Exchange or the
New York Stock Exchange.

         T. Underwriting Agreement shall mean the agreement between the
Corporation and the underwriter or underwriters managing the initial public
offering of the Common Stock.