
<PAGE>   1

                                                                     EXHIBIT 3.1

                                    RESTATED

                          CERTIFICATE OF INCORPORATION

                                       OF

                                  STAPLES, INC.

                     PURSUANT TO SECTION 245 OF THE GENERAL
                    CORPORATION LAW OF THE STATE OF DELAWARE
                    ----------------------------------------



                                    ARTICLE I
                                    ---------

                                      NAME
                                      ----

     The name of the corporation is: Staples, Inc.

                                   ARTICLE II
                                   ----------

                                    PURPOSES
                                    --------

     The purpose of the Corporation is to engage in any lawful act or activity
for which a corporation may be organized under the General Corporation Law of
Delaware other than the banking business, the trust company business or the
practice of a profession permitted to be incorporated by the General Corporation
Code.

                                   ARTICLE III
                                   -----------

                                AGENT FOR SERVICE
                                -----------------

     The name and address in the State of Delaware of this Corporation's
registered agent for service of process is:

     The Corporation Trust Company

                                        1

<PAGE>   2



     1209 Orange Street
     Wilmington, New Castle County, Delaware 19801

                                   ARTICLE IV
                                   ----------

                                  CAPITAL STOCK
                                  -------------

     The total number of shares of all classes of stock which the Corporation
has authority to issue is one billion five million (1,005,000,000) shares,
consisting of one billion (1,000,000,000) shares of Common Stock with a par
value of $.0006 per share ("Common Stock") and five million (5,000,000) shares
of Preferred Stock with a par value of $.01 per share ("Preferred Stock").

     (a)  COMMON STOCK

     SECTION 1. VOTING RIGHTS. The holders of shares of Common Stock shall be
entitled to one vote for each share so held with respect to all matters voted on
by the stockholders of the Corporation.

     SECTION 2. LIQUIDATION RIGHTS. Upon the dissolution, liquidation or winding
up of the Corporation, after any preferential amounts to be distributed to the
holders of any series of Preferred Stock then outstanding have been paid or
declared and set apart for payment, and subject to the rights, if any, of the
holders of any series of Preferred Stock then outstanding to share in any
remaining assets of the Corporation, the holders of the Common Stock will be
entitled to receive all the remaining assets of the Corporation available for
distribution to its stockholders ratably in proportion to the number of shares
held by them, respectively.

     SECTION 3. DIVIDENDS. To the extent permitted under the General Corporation
Law of Delaware and subject to the rights, if any, of the Preferred Stock,
dividends may be paid on the Common Stock as and when declared by the Board of
Directors.

     (b)  PREFERRED STOCK

     SECTION 1. DESIGNATION. The Preferred Stock shall be designated and known
as "Preferred Stock." The number of shares constituting such Preferred Stock
shall be 5,000,000.


                                        2


<PAGE>   3




     SECTION 2. RIGHTS AND PREFERENCES. The Board of Directors is authorized,
subject to limitations prescribed by law and this Amended and Restated
Certificate of Incorporation, to divide the Preferred Stock into series and to
establish and designate each series and fix and determine the variations in the
relative rights and preferences as between the different series, provided that
all shares of the Preferred Stock shall be identical except that the Board of
Directors shall be authorized to fix and determine:

     (a)  the number of shares in and the distinctive designation of each
series;

     (b)  whether or not the shares of any series shall be redeemable and, if
so, the price (which may vary under different conditions and at different
redemption dates), terms and manner of redemption, including the date or dates
on or after which they shall be redeemable;

     (c)  special and relative rights as to dividends with respect to each
series, including without limitation the dividend rate, conditions under which
dividends may be payable, dividend preferences, if any, and whether and from
which date or dates dividends may be cumulative;

     (d)  special and relative rights with respect to each series on
liquidation, voluntary or involuntary, including dissolution or winding up of
the Corporation;

     (e)  any sinking fund or purchase fund provisions applicable to any series,
including without limitation the annual amount thereof and the terms relating
thereto;

     (f)  conversion rights, if any, of each series including the terms and
conditions of conversion, which may contain provisions for adjustment of the
conversion rate in such events as the Board of Directors shall determine; and

     (g)  conditions under which the separate series shall have voting rights or
no voting rights, in addition to the voting rights provided by law.

     Prior to the issue of any shares of a series established by the Directors,
there shall be filed with the Secretary of State of the State of Delaware a
certificate required by law setting forth the designation of the series, its
relative rights and preferences and any other information required by law.



                                        3

<PAGE>   4




     (c)  SERIES A JUNIOR PARTICIPATING PREFERRED STOCK

     RESOLVED, that pursuant to the authority granted to and vested in the Board
of Directors of this Corporation (hereinafter called the "Board of Directors" or
the "Board") in accordance with the provisions of the Certificate of
Incorporation (as amended to date, the "Certificate of Incorporation"), the
Board of Directors hereby creates a series of Preferred Stock, $.01 par value
per share (the "Preferred Stock"), of the Corporation and hereby states the
designation and number of shares, and fixes the relative rights, preferences and
limitations thereof as follows:

     SECTION 1. DESIGNATION AND AMOUNT.

     The shares of such series shall be designated as "Series A Junior
Participating Preferred Stock" (the "Series A Preferred Stock") and the number
of shares constituting the Series A Preferred Stock shall be 1,000,000. Such
number of shares may be increased or decreased by resolution of the Board of
Directors; PROVIDED, that no decrease shall reduce the number of shares of
Series A Preferred Stock to a number less than the number of shares then
outstanding plus the number of shares reserved for issuance upon the exercise of
outstanding options, rights or warrants or upon the conversion of any
outstanding securities issued by the Corporation convertible into Series A
Preferred Stock.

     SECTION 2. DIVIDENDS AND DISTRIBUTIONS.

     (a)  Subject to the rights of the holders of any shares of any series of
Preferred Stock (or any similar stock) ranking prior and superior to the Series
A Preferred Stock with respect to dividends, the holders of shares of Series A
Preferred Stock, in preference to the holders of Common Stock, par value $.0006
per share (the "Common Stock"), of the Corporation, and of any other junior
stock, shall be entitled to receive, when, as and if declared by the Board of
Directors out of funds of the Corporation legally available for the payment of
dividends, quarterly dividends payable in cash on March 31, June 30, September
30 and December 31 in each year (each such date being referred to herein as a
"Quarterly Dividend Payment Date"), commencing on the first Quarterly Dividend
Payment Date after the first issuance of a share or fraction of a share of
Series A Preferred Stock, in an amount per share (rounded to the nearest cent)
equal to the greater of (a) $1 or (b) subject to the provision for adjustment
hereinafter set forth, 100 times the aggregate per share amount of all cash
dividends, and 100 times the aggregate per share amount (payable in kind) of all
non-cash dividends or other distributions, other than a dividend payable in
shares of Common Stock or a subdivision of the outstanding shares of Common
Stock (by reclassification or otherwise), declared on the Common Stock since the
immediately preceding Quarterly Dividend Payment Date or, with respect to the
first Quarterly Dividend Payment Date, since the first issuance of any share or

                                        4

<PAGE>   5



fraction of a share of Series A Preferred Stock. In the event the Corporation
shall at any time declare or pay any dividend on the Common Stock payable in
shares of Common Stock, or effect a subdivision, combination or consolidation of
the outstanding shares of Common Stock (by reclassification or otherwise than by
payment of a dividend in shares of Common Stock) into a greater or lesser number
of shares of Common Stock, then in each such case the amount to which holders of
shares of Series A Preferred Stock were entitled immediately prior to such event
under clause (b) of the preceding sentence shall be adjusted by multiplying such
amount by a fraction, the numerator of which is the number of shares of Common
Stock outstanding immediately after such event and the denominator of which is
the number of shares of Common Stock that were outstanding immediately prior to
such event.

     (b)  The Corporation shall declare a dividend or distribution on the Series
A Preferred Stock as provided in paragraph (A) of this Section immediately after
it declares a dividend or distribution on the Common Stock (other than a
dividend payable in shares of Common Stock) and the Corporation shall pay such
dividend or distribution on the Series A Preferred Stock before the dividend or
distribution declared on the Common Stock is paid or set apart; provided that,
in the event no dividend or distribution shall have been declared on the Common
Stock during the period between any Quarterly Dividend Payment Date and the next
subsequent Quarterly Dividend Payment Date, a dividend of $1 per share on the
Series A Preferred Stock shall nevertheless be payable on such subsequent
Quarterly Dividend Payment Date.

     (c)  Dividends shall begin to accrue and be cumulative on outstanding
shares of Series A Preferred Stock from the Quarterly Dividend Payment Date next
preceding the date of issue of such shares, unless the date of issue of such
shares is prior to the record date for the first Quarterly Dividend Payment
Date, in which case dividends on such shares shall begin to accrue from the date
of issue of such shares, or unless the date of issue is a Quarterly Dividend
Payment Date or is a date after the record date for the determination of holders
of shares of Series A Preferred Stock entitled to receive a quarterly dividend
and before such Quarterly Dividend Payment Date, in either of which events such
dividends shall begin to accrue and be cumulative from such Quarterly Dividend
Payment Date. Accrued but unpaid dividends shall not bear interest. Dividends
paid on the shares of Series A Preferred Stock in an amount less than the total
amount of such dividends at the time accrued and payable on such shares shall be
allocated pro rata on a share-by-share basis among all such shares at the time
outstanding. The Board of Directors may fix a record date for the determination
of holders of shares of Series A Preferred Stock entitled to receive payment of
a dividend or distribution declared thereon, which record date shall be not more
than 60 days prior to the date fixed for the payment thereof.


                                        5

<PAGE>   6



     SECTION 3. VOTING RIGHTS.

     The holders of shares of Series A Preferred Stock shall have the following
voting rights:

     (a)  Subject to the provision for adjustment hereinafter set forth, each
share of Series A Preferred Stock shall entitle the holder thereof to 100 votes
on all matters submitted to a vote of the stockholders of the Corporation. In
the event the Corporation shall at any time declare or pay any dividend on the
Common Stock payable in shares of Common Stock, or effect a subdivision,
combination or consolidation of the outstanding shares of Common Stock (by
reclassification or otherwise than by payment of a dividend in shares of Common
Stock) into a greater or lesser number of shares of Common Stock, then in each
such case the number of votes per share to which holders of shares of Series A
Preferred Stock were entitled immediately prior to such event shall be adjusted
by multiplying such number by a fraction, the numerator of which is the number
of shares of Common Stock outstanding immediately after such event and the
denominator of which is the number of shares of Common Stock that were
outstanding immediately prior to such event.

     (b)  Except as otherwise provided herein, by law, or in any other
Certificate of Designations creating a series of Preferred Stock or any similar
stock, the holders of shares of Series A Preferred Stock and the holders of
shares of Common Stock and any other capital stock of the Corporation having
general voting rights shall vote together as one class on all matters submitted
to a vote of stockholders of the Corporation.

     (c)  (i)       If any time dividends on any Series A Preferred Stock shall
be in arrears in an amount equal to six quarterly dividends thereon, the holders
of the Series A Preferred Stock, voting as a separate series from all other
series of Preferred Stock and classes of capital stock, shall be entitled to
elect two members of the Board of Directors in addition to any Directors elected
by any other series, class or classes of securities and the authorized number of
Directors will automatically be increased by two. Promptly thereafter, the Board
of Directors of this Corporation shall, as soon as may be practicable, call a
special meeting of holders of Series A Preferred Stock for the purpose of
electing such members of the Board of Directors. Said special meeting shall in
any event be held within 45 days of the occurrence of such arrearage.

          (ii)      During any period when the holders of Series A Preferred
Stock, voting as a separate series, shall be entitled and shall have exercised
their right to elect two Directors, then and during such time as such right
continues (a) the then authorized number of Directors shall be increased by two,
and the holders of Series A Preferred Stock, voting as a separate series, shall
be entitled to elect the additional Director so provided for, and (b) each such
additional Director shall not be a member

                                        6

<PAGE>   7



of any existing class of the Board of Directors, but shall serve until the next
annual meeting of stockholders for the election of Directors, or until his
successor shall be elected and shall qualify, or until his right to hold such
office terminates pursuant to the provisions of this Section 3(c).

          (iii)     A Director elected pursuant to the terms hereof may be
removed with or without cause by the holders of Series A Preferred Stock
entitled to vote in an election of such Director.

          (iv)      If, during any interval between annual meetings of
stockholders for the election of Directors and while the holders of Series A
Preferred Stock shall be entitled to elect two Directors, there is no such
Director in office by reason of resignation, death or removal, then, promptly
thereafter, the Board of Directors shall cause a special meeting of the holders
of Series A Preferred Stock for the purpose of filling such vacancy and such
vacancy shall be filled at such special meeting. Such special meeting shall in
any event be held within 45 days of the occurrence of such vacancy.

          (v)       At such time as the arrearage is fully cured, and all
dividends accumulated and unpaid on any shares of Series A Preferred Stock
outstanding are paid, and, in addition thereto, at least one regular dividend
has been paid subsequent to curing such arrearage, the term of office of any
Director elected pursuant to this Section 3(c), or his successor, shall
automatically terminate, and the authorized number of Directors shall
automatically decrease by two, the rights of the holders of the shares of the
Series A Preferred Stock to vote as provided in this Section 3(c) shall cease,
subject to renewal from time to time upon the same terms and conditions, and the
holders of shares of the Series A Preferred Stock shall have only the limited
voting rights elsewhere herein set forth.

     (d)  Except as set forth herein, or as otherwise provided by law, holders
of Series A Preferred Stock shall have no special voting rights and their
consent shall not be required (except to the extent they are entitled to vote
with holders of Common Stock as set forth herein) for taking any corporate
action.

     SECTION 4. CERTAIN RESTRICTIONS.

     (a)  Whenever quarterly dividends or other dividends or distributions
payable on the Series A Preferred Stock as provided in Section 2 are in arrears,
thereafter and until all accrued and unpaid dividends and distributions, whether
or not declared, on shares of Series A Preferred Stock outstanding shall have
been paid in full, the Corporation shall not:

          (i)       declare or pay dividends, or make any other distributions,
on any shares of stock ranking junior (either as to dividends or upon
liquidation, dissolution

                                        7

<PAGE>   8



or winding up) to the Series A Preferred Stock;

          (ii)      declare or pay dividends, or make any other distributions,
on any shares of stock ranking on a parity (either as to dividends or upon
liquidation, dissolution or winding up) with the Series A Preferred Stock,
except dividends paid ratably on the Series A Preferred Stock and all such
parity stock on which dividends are payable or in arrears in proportion to the
total amounts to which the holders of all such shares are then entitled;

          (iii)     redeem or purchase or otherwise acquire for consideration
shares of any stock ranking junior (either as to dividends or upon liquidation,
dissolution or winding up) to the Series A Preferred Stock, provided that the
Corporation may at any time redeem, purchase or otherwise acquire shares of any
such junior stock in exchange for shares of any stock of the Corporation ranking
junior (either as to dividends or upon dissolution, liquidation or winding up)
to the Series A Preferred Stock; or (iv) redeem or purchase or otherwise acquire
for consideration any shares of Series A Preferred Stock, or any shares of stock
ranking on a parity with the Series A Preferred Stock, except in accordance with
a purchase offer made in writing or by publication (as determined by the Board
of Directors) to all holders of such shares upon such terms as the Board of
Directors, after consideration of the respective annual dividend rates and other
relative rights and preferences of the respective series and classes, shall
determine in good faith will result in fair and equitable treatment among the
respective series or classes.

     (b)  The Corporation shall not permit any subsidiary of the Corporation to
purchase or otherwise acquire for consideration any shares of stock of the
Corporation unless the Corporation could, under paragraph (a) of this Section 4,
purchase or otherwise acquire such shares at any time and in such manner.

     SECTION 5. REACQUIRED SHARES.

     Any shares of Series A Preferred Stock purchased or otherwise acquired by
the Corporation in any manner whatsoever shall be retired and cancelled promptly
after the acquisition thereof. All such shares shall upon their cancellation
become authorized but unissued shares of Preferred Stock and may be reissued as
part of a new series of Preferred Stock subject to the conditions and
restrictions on issuance set forth herein, in the Restated Certificate of
Incorporation, as amended, or in any other Certificate of Designations creating
a series of Preferred Stock or any similar stock or as otherwise required by
law.

     SECTION 6. LIQUIDATION, DISSOLUTION OR WINDING UP

     (a)  Upon any liquidation, dissolution or winding up of the Corporation, no
distribution shall be made (1) to the holders of shares of stock ranking junior
(either

                                        8

<PAGE>   9



as to dividends or upon liquidation, dissolution or winding up) to the Series A
Preferred Stock unless, prior thereto, the holders of shares of Series A
Preferred Stock shall have received $100 per share, plus an amount equal to
accrued and unpaid dividends and distributions thereon, whether or not declared,
to the date of such payment, provided that the holders of shares of Series A
Preferred Stock shall be entitled to receive an aggregate amount per share,
subject to the provision for adjustment hereinafter set forth, equal to 100
times the aggregate amount to be distributed per share to holders of shares of
Common Stock, or (2) to the holders of shares of stock ranking on a parity
(either as to dividends or upon liquidation, dissolution or winding up) with the
Series A Preferred Stock, except distributions made ratably on the Series A
Preferred Stock and all such parity stock in proportion to the total amounts to
which the holders of all such shares are entitled upon such liquidation,
dissolution or winding up.

     (b)  Neither the consolidation, merger or other business combination of the
Corporation with or into any other corporation nor the sale, lease, exchange or
conveyance of all or any part of the property, assets or business of the
Corporation shall be deemed to be a liquidation, dissolution or winding up of
the Corporation for purposes of this Section 6.

     (c)  In the event the Corporation shall at any time declare or pay any
dividend on the Common Stock payable in shares of Common Stock, or effect a
subdivision, combination or consolidation of the outstanding shares of Common
Stock (by reclassification or otherwise than by payment of a dividend in shares
of Common Stock) into a greater or lesser number of shares of Common Stock, then
in each such case the aggregate amount to which holders of shares of Series A
Preferred Stock were entitled immediately prior to such event under the proviso
in clause (1) of paragraph (a) of this Section 6 shall be adjusted by
multiplying such amount by a fraction the numerator of which is the number of
shares of Common Stock outstanding immediately after such event and the
denominator of which is the number of shares of Common Stock that were
outstanding immediately prior to such event.

     SECTION 7. CONSOLIDATION, MERGER, ETC.

     Notwithstanding anything to the contrary contained herein, in case the
Corporation shall enter into any consolidation, merger, combination or other
transaction in which the shares of Common Stock are exchanged for or changed
into other stock or securities, cash and/or any other property, then in any such
case each share of Series A Preferred Stock shall at the same time be similarly
exchanged or changed into an amount per share, subject to the provision for
adjustment hereinafter set forth, equal to 100 times the aggregate amount of
stock, securities, cash and/or any other property (payable in kind), as the case
may be, into which or for which each share of Common Stock is changed or
exchanged. In the event the Corporation

                                        9

<PAGE>   10



shall at any time declare or pay any dividend on the Common Stock payable in
shares of Common Stock, or effect a subdivision, combination or consolidation of
the outstanding shares of Common Stock (by reclassification or otherwise than by
payment of a dividend in shares of Common Stock) into a greater or lesser number
of shares of Common Stock, then in each such case the amount set forth in the
preceding sentence with respect to the exchange or change of shares of Series A
Preferred Stock shall be adjusted by multiplying such amount by a fraction, the
numerator of which is the number of shares of Common Stock outstanding
immediately after such event and the denominator of which is the number of
shares of Common Stock that were outstanding immediately prior to such event.

     SECTION 8. NO REDEMPTION.

     The shares of Series A Preferred Stock shall not be redeemable.

     SECTION 9. RANK.

     The Series A Preferred Stock shall rank, with respect to the payment of
dividends and the distribution of assets, junior to all series of any other
class of the Preferred Stock issued either before or after the issuance of the
Series A Preferred Stock, unless the terms of any such series shall provide
otherwise.

     SECTION 10. AMENDMENT.

     The Restated Certificate of Incorporation, as amended, of the Corporation
shall not be amended in any manner which would materially alter or change the
powers, preferences or special rights of the Series A Preferred Stock so as to
affect them adversely without the affirmative vote of the holders of at least
two-thirds of the outstanding shares of Series A Preferred Stock, voting
together as a single class.

     SECTION 11. FRACTIONAL SHARES.

     Series A Preferred Stock may be issued in fractions of a share which are
integral multiples of one-hundredth of a share which shall entitle the holder,
in proportion to such holder's fractional shares, to exercise voting rights,
receive dividends, participate in distributions and have the benefit of all
other rights of holders of Series A Preferred Stock.


                                       10

<PAGE>   11




                                    ARTICLE V
                                    ---------
                                 INDEMNIFICATION
                                 ---------------

     The Corporation shall indemnify its present and former directors and
officers to the maximum extent permitted by the General Corporation Law as from
time to time amended. The indemnification provided for herein shall not be
deemed exclusive of any other rights to which those seeking indemnification may
be entitled under any by-law, agreement, vote of stockholders or disinterested
directors or otherwise.


                                   ARTICLE VI
                                    --------
                                    EXISTENCE
                                   -----------

     The Corporation is to have perpetual existence.


                                   ARTICLE VII
                                   -----------
                                     BY-LAWS
                                     -------

     In furtherance and not in limitation of the powers conferred by statute,
the Board of Directors is expressly authorized to make, alter or repeal the
By-Laws of the Corporation.


                                  ARTICLE VIII
                                  ------------
                         STOCKHOLDER MEETINGS AND BOOKS
                         ------------------------------

     Meetings of stockholders may be held within or without the State of
Delaware, as the By-Laws may provide. The books of the Corporation may be kept
(subject to any provisions contained in the statutes) outside the State of
Delaware at such place or places as may be designated from time to time by the
Board of Directors or in the By-Laws of the Corporation.


                                       11

<PAGE>   12




                                   ARTICLE IX
                                   ----------
                                    AMENDMENT
                                    ---------

     The Corporation reserves the right to end, alter, change or repeal any
provision contained in this Amended and Restated Certificate of Incorporation,
in the manner now or hereafter prescribed by statute, and all rights conferred
upon stockholders herein are granted subject to this reservation.


                                    ARTICLE X
                                    ---------
                        LIMITATION ON DIRECTOR LIABILITY
                        --------------------------------

     No director of the Corporation shall be liable to the Corporation or its
stockholders for monetary damages for breach of fiduciary duty as a director,
except for liability (i) for any breach of the director's duty of loyalty to the
Corporation or its stockholders, (ii) for acts or omissions not in good faith or
which involve intentional misconduct or a knowing violation of law, (iii) under
Section 174 of the Delaware General Corporation law, or (iv) for any transaction
in which the director derived an improper personal benefit. Any repeal or
modification of the foregoing paragraph by the stockholders of the Corporation
shall not adversely affect any right or protection of a director of the
Corporation existing at the time of such repeal or modification.


                                   ARTICLE XI
                                   ----------
                                MEETINGS REQUIRED
                                -----------------

     Any action required or permitted to be taken by the stockholders of the
Corporation must be effected at a duly called annual or special meeting of
stockholders of the Corporation and may not be effected by any consent in
writing by such stockholders.


                                       12

<PAGE>   13



                                   ARTICLE XII
                                   -----------
                           CERTAIN STOCKHOLDER ACTION
                           --------------------------

     The following actions shall require the affirmative vote of two-thirds of
the stock of this Corporation outstanding and entitled to vote thereon: the
sale, lease or exchange of all or substantially all of this Corporation's
property and assets; the merger or consolidation of this Corporation with or
into any other corporation or entity; the dissolution of this Corporation; and
the amendment or repeal of this Article XII or the adoption of any provision
inconsistent with this Article XII.

     This Amended and Restated Certificate of Incorporation supersedes and takes
the place of the heretofore existing Restated Certificate of Incorporation, as
amended, of this Corporation and all amendments, certificates and supplements
thereto, if any.






                                       13


