<PAGE>

       As filed with the Securities and Exchange Commission on May 1, 2000
                                                      Registration No. 333-_____

                                  UNITED STATES
                       SECURITIES AND EXCHANGE COMMISSION
                             WASHINGTON, D.C. 20549
                             -----------------------

                                    FORM S-8
                        REGISTRATION STATEMENT UNDER THE
                             SECURITIES ACT OF 1933
                             -----------------------

                              PAPER WAREHOUSE, INC.
             (Exact name of registrant as specified in its charter)

                  MINNESOTA                             41-1612534
        (State or other jurisdiction of              (I.R.S. Employer
        incorporation or organization)              Identification No.)

            7630 EXCELSIOR BOULEVARD
             MINNEAPOLIS, MINNESOTA                        55426
    (Address of Principal Executive Offices)             (Zip Code)
                             -----------------------

                              PAPER WAREHOUSE, INC.
                              AMENDED AND RESTATED
                        1998 EMPLOYEE STOCK PURCHASE PLAN
                            (Full title of the plan)

                             -----------------------

                                YALE T. DOLGINOW
                      PRESIDENT AND CHIEF EXECUTIVE OFFICER
                              PAPER WAREHOUSE, INC.
                            7630 EXCELSIOR BOULEVARD
                              MINNEAPOLIS, MN 55426
                                 (952) 936-1000
                      (Name, address and telephone number,
                   including area code, of agent for service)

                              --------------------
<TABLE>
<CAPTION>

                         CALCULATION OF REGISTRATION FEE
===================================================================================================================
                                                                            PROPOSED MAXIMUM
  TITLE OF SECURITIES TO     AMOUNT TO BE     PROPOSED MAXIMUM OFFERING    AGGREGATE OFFERING       AMOUNT OF
       BE REGISTERED        REGISTERED (1)        PRICE PER UNIT (2)             PRICE           REGISTRATION FEE
-------------------------------------------------------------------------------------------------------------------
 <S>                        <C>               <C>                          <C>                   <C>
 Common Stock, $.01 par
 value per share                 150,000                 $.94                   $141,000               $37
===================================================================================================================
</TABLE>

(1)  In addition, pursuant to Rule 416(c) under the Securities Act of 1933,
     as amended, this Registration Statement also covers an
     indeterminate number of additional shares that may be offered and
     sold as a result of anti-dilution provisions described in the
     Amended and Restated 1998 Employee Stock Purchase Plan.

(2)  Estimated pursuant to Rule 457(h) under the Securities Act solely for
     the purpose of calculating the amount of the registration fee as
     follows: (i) with respect to options to purchase shares previously
     granted under the plan, on the basis of the weighted average exercise
     price of such option grants, and (ii) with respect to options to be
     granted under the plan, on the basis of the average between the high and
     low reported sales prices of the Registrant's common stock on April 25,
     2000, on the over-the-counter market, as reported by the Nasdaq National
     Market.

<PAGE>

                                     PART I

                              INFORMATION REQUIRED
                         IN THE SECTION 10(a) PROSPECTUS


         The documents containing the information specified in Part I of Form
S-8 have been or will be sent or given to participants as specified by Rule
428(b)(1) under the Securities Act.


                                     PART II

                              INFORMATION REQUIRED
                          IN THE REGISTRATION STATEMENT

ITEM 3.  INCORPORATION OF DOCUMENTS BY REFERENCE.

         The following documents filed by Paper Warehouse, Inc. (File No.
0-23389) with the Securities and Exchange Commission are incorporated by
reference in this Registration Statement:

         (1) Paper Warehouse's latest Annual Report on Form 10-K for the fiscal
year ended January 28, 2000;

         (2) All other reports filed by Paper Warehouse pursuant to Sections
13(a) or 15(d) of the Securities Exchange Act of 1934 since January 28, 2000;
and

         (3) The description of Paper Warehouse's common stock contained in its
Registration Statement on Form 8-A filed with the Commission on November 18,
1997 under the Exchange Act, including any amendments or reports filed for the
purpose of updating such description.

         All documents filed by Paper Warehouse with the Commission pursuant to
Sections 13(a), 13(c), 14 and 15(d) of the Exchange Act after the date of this
Registration Statement and prior to the filing of a post-effective amendment
which indicates that all securities offered pursuant to this Registration
Statement have been sold or that deregisters all securities then remaining
unsold, shall be deemed to be incorporated by reference in this Registration
Statement and to be a part hereof from the date of filing of such documents.

ITEM 4.  DESCRIPTION OF SECURITIES.

         Not applicable.

ITEM 5.  INTERESTS OF NAMED EXPERTS AND COUNSEL.

         The validity of the securities that may be offered under the Paper
Warehouse, Inc. Amended and Restated 1998 Employee Stock Purchase Plan will be
passed upon for Paper Warehouse by Oppenheimer Wolff & Donnelly LLP,
Minneapolis, Minnesota.

ITEM 6.  INDEMNIFICATION OF DIRECTORS AND OFFICERS.

         Paper Warehouse's Articles of Incorporation limit the liability of its
directors to the fullest extent permitted by the Minnesota Business Corporation
Act. Specifically, directors of Paper Warehouse will


                                       1
<PAGE>

not be personally liable for monetary damages for breach of fiduciary duty as
directors, except liability for (i) any breach of the duty of loyalty to Paper
Warehouse or its shareholders, (ii) acts or omissions not in good faith or that
involve intentional misconduct or a knowing violation of law, (iii) dividends or
other distributions of corporate assets that are in contravention of certain
statutory or contractual restrictions, (iv) violations of certain Minnesota
securities laws, or (v) any transaction from which the director derives an
improper personal benefit. Liability under federal securities law is not limited
by Paper Warehouse's Articles of Incorporation.

         Minnesota Statutes, Section 302A.521 provides that a Minnesota business
corporation shall indemnify any director, officer, employee or agent of the
corporation made or threatened to be made a party to a proceeding, by reason of
the former or present official capacity (as defined) of the person, against
judgments, penalties, fines, settlements and reasonable expenses incurred by the
person in connection with the proceeding if certain statutory standards are met.
"Proceeding" means a threatened, pending or completed civil, criminal,
administrative, arbitration or investigative proceeding, including one by or in
the right of the corporation. Section 302A.521 contains detailed terms regarding
such right of indemnification and reference is made thereto for a complete
statement of such indemnification rights. Paper Warehouse's Articles of
Incorporation and Bylaws also require Paper Warehouse to provide indemnification
to the fullest extent of the Minnesota indemnification statute.

         Paper Warehouse also maintains a directors and officers insurance
policy pursuant to which directors and officers of Paper Warehouse are insured
against liability for certain actions in their capacity as directors and
officers.

ITEM 7.  EXEMPTIONS FROM REGISTRATION CLAIMED.

         Not applicable. No securities are to be reoffered or resold pursuant to
this Registration Statement.

ITEM 8.  EXHIBITS.

EXHIBIT NO.

5.1       Opinion of Oppenheimer Wolff & Donnelly LLP (filed herewith).

23.1      Consent of  Grant Thornton LLP (filed herewith).

23.2      Consent of KPMG LLP (filed herewith).

23.3      Consent of Oppenheimer Wolff & Donnelly LLP (included in Exhibit 5.1).

24.1      Power of Attorney (included on page 6 of this Registration Statement).


ITEM 9.  UNDERTAKINGS.

     (a) The undersigned Registrant hereby undertakes:

              (1)     To file, during any period in which offers or sales are
                      being made, a post-effective amendment to this
                      Registration Statement:

                      (i)      To include any prospectus required by Section
                               10(a)(3) of the Securities Act;


                                       2
<PAGE>

                      (ii)      To reflect in the prospectus any facts or events
                                arising after the effective date of this
                                Registration Statement (or the most recent
                                post-effective amendment hereof) which,
                                individually or in the aggregate, represent a
                                fundamental change in the information set forth
                                in this Registration Statement. Notwithstanding
                                the foregoing, any increase or decrease in
                                volume of securities offered (if the total
                                dollar value of securities offered would not
                                exceed that which was registered) and any
                                deviation from the low or high end of the
                                estimated maximum offering range may be
                                reflected in the form of prospectus filed with
                                the Commission pursuant to Rule 424(b) under the
                                Securities Act if, in the aggregate, the changes
                                in volume and price represent no more than a 20%
                                change in the maximum aggregate offering price
                                set forth in the "Calculation of Registration
                                Fee" table in the effective Registration
                                Statement;

                      (iii)    To include any material information with respect
                               to the plan of distribution not previously
                               disclosed in the Registration Statement or any
                               material change to such information in this
                               Registration Statement.

                      PROVIDED, HOWEVER, that paragraphs (a)(1)(i) and
                      (a)(1)(ii) above do not apply if the information required
                      to be included in a post-effective amendment by those
                      paragraphs is contained in periodic reports filed with or
                      furnished to the Commission by the Registrant pursuant to
                      Section 13 or Section 15(d) of the Exchange Act that are
                      incorporated by reference in this Registration Statement.

              (2)     That, for the purpose of determining any liability under
                      the Securities Act, each such post-effective amendment
                      shall be deemed to be a new registration statement
                      relating to the securities offered therein, and the
                      offering of such securities at that time shall be deemed
                      to be the initial bona fide offering thereof.

              (3)     To remove from registration by means of a post-effective
                      amendment any of the securities being registered which
                      remain unsold at the termination of the offering.

     (b)      The undersigned Registrant hereby undertakes that, for purposes of
              determining any liability under the Securities Act, each filing of
              the Registrant's annual report pursuant to Section 13(a) or
              Section 15(d) of the Exchange Act (and where applicable, each
              filing of an employee benefit plan's annual report pursuant to
              Section 15(d) of the Exchange Act) that is incorporated by
              reference in this Registration Statement shall be deemed to be a
              new registration statement relating to the securities offered
              therein, and the offering of such securities at that time shall be
              deemed to be the initial bona fide offering thereof.

     (c)      Insofar as indemnification for liabilities arising under the
              Securities Act may be permitted to directors, officers and
              controlling persons of the Registrant pursuant to the foregoing
              provisions, or otherwise, the Registrant has been advised that in
              the opinion of the Commission such indemnification is against
              public policy as expressed in the Securities Act, and is
              therefore, unenforceable. In the event that a claim for
              indemnification against such liabilities (other than the payment
              by the Registrant of expenses incurred or paid by a director,
              officer or controlling person of the Registrant in the successful
              defense of any action, suit or proceeding) is asserted by such
              director, officer or controlling person in connection with the
              securities being registered, the Registrant will, unless in the
              opinion of its counsel the matter has been settled by controlling
              precedent, submit to a court of appropriate


                                       3
<PAGE>

              jurisdiction the question whether such indemnification by it is
              against public policy as expressed in the Securities Act and will
              be governed by the final adjudication of such issue.


                                       4
<PAGE>



                                   SIGNATURES

     Pursuant to the requirements of the Securities Act of 1933, the Registrant
certifies that it has reasonable grounds to believe that it meets all of the
requirements for filing on Form S-8 and has duly caused this Registration
Statement to be signed on its behalf by the undersigned, thereunto duly
authorized, in the City of Minneapolis, State of Minnesota, on May 1, 2000.

                            PAPER WAREHOUSE, INC.

                               By: /s/ Yale T. Dolginow
                                  ----------------------------------------------
                                   Yale T. Dolginow
                                   President and Chief Executive Officer
                                   (principal executive officer)


                               By: /s/ Cheryl W. Newell
                                  ----------------------------------------------
                                   Cheryl W. Newell
                                   Vice President and Chief Financial Officer
                                   (principal financial  officer)


                               By: /s/ Diana G. Purcel
                                  ----------------------------------------------
                                   Diana G. Purcel
                                   Controller
                                   (principal accounting officer)


                                       5

<PAGE>

                                POWER OF ATTORNEY

     Each person whose signature appears below constitutes and appoints Yale T.
Dolginow and Cheryl W. Newell, and each of them, his or her true and lawful
attorney-in-fact and agent with full powers of substitution and resubstitution,
for and in his or her name, place and stead, in any and all capacities, to sign
any or all amendments (including post-effective amendments) to this Registration
Statement, and to file the same, with all exhibits thereto, and other documents
in connection therewith, with the Securities and Exchange Commission, granting
unto said attorney-in-fact and agent full power and authority to do and perform
each and every act and thing requisite or necessary to be done in and about the
premises, as fully to all intents and purposes as he or she might or could do in
person, hereby ratifying and confirming all that said attorney-in-fact and agent
or his or her substitute or substitutes, may lawfully do or cause to be done by
virtue thereof.

     Pursuant to the requirements of the Securities Act of 1933, this
Registration Statement has been signed on May 1, 2000 by the following persons
in the capacities indicated.

<TABLE>
<CAPTION>

SIGNATURE                            TITLE
---------                            -----
<S>                                  <C>

/s/ Yale T. Dolginow
----------------------------         President and Chief Executive Officer
Yale T. Dolginow                     and Director, Chairman of the Board

/s/ Arthur H. Cobb
----------------------------         Director
Arthur H. Cobb

/s/ Diane C. Dolginow
----------------------------         Secretary and Director
Diane C. Dolginow

/s/ Marvin W. Goldstein
----------------------------         Director
Marvin W. Goldstein

/s/ Jeffrey S. Halpern
----------------------------         Director
Jeffrey S. Halpern

/s/ Martin A. Mayer
----------------------------         Director
Martin A. Mayer

/s/ Cheryl W. Newell
----------------------------         Vice President and Chief Financial Officer
Cheryl W. Newell

/s/ Diana G. Purcel
----------------------------         Controller
Diana G. Purcel
</TABLE>


                                       6
<PAGE>

<TABLE>
<CAPTION>
                                INDEX TO EXHIBITS


 NO.                              ITEM                             METHOD OF FILING
 --                               ----                             ----------------
<C>       <S>                                                      <C>
5.1       Opinion of Oppenheimer Wolff & Donnelly LLP..............Filed herewith.

23.1      Consent of  Grant Thornton LLP...........................Filed herewith

23.2      Consent of KPMG LLP......................................Filed herewith.

23.3      Consent of Oppenheimer Wolff & Donnelly LLP..............Included in Exhibit 5.1.

24.1      Power of Attorney........................................Included on page 6 of this Registration
                                                                   Statement.
</TABLE>
[{"type": "S-8", "sequence": "1", "description": "S-8", "secsgml_size_bytes": 19223}]
{"company-data": {"conformed-name": "PAPER WAREHOUSE INC", "cik": "0000934509", "assigned-sic": "5940", "irs-number": "411612534", "state-of-incorporation": "MN", "fiscal-year-end": "0131"}, "filing-values": {"form-type": "S-8", "act": "33", "file-number": "333-36066", "film-number": "616600"}, "business-address": {"street1": "7630 EXCELSIOR BLVD", "city": "MINNEAPOLIS", "state": "MN", "zip": "55416", "phone": "6129361000"}, "mail-address": {"street1": "7630 EXCELSIOR BLVD", "city": "MINNEAPOLIS", "state": "MN", "zip": "55416"}}
As filed with the Securities and Exchange Commission on May 1, 2000
                                                      Registration No. 333-_____

                                  UNITED STATES
                       SECURITIES AND EXCHANGE COMMISSION
                             WASHINGTON, D.C. 20549
                             -----------------------

                                    FORM S-8
                        REGISTRATION STATEMENT UNDER THE
                             SECURITIES ACT OF 1933
                             -----------------------

                              PAPER WAREHOUSE, INC.
             (Exact name of registrant as specified in its charter)

                  MINNESOTA                             41-1612534
        (State or other jurisdiction of              (I.R.S. Employer
        incorporation or organization)              Identification No.)

            7630 EXCELSIOR BOULEVARD
             MINNEAPOLIS, MINNESOTA                        55426
    (Address of Principal Executive Offices)             (Zip Code)
                             -----------------------

                              PAPER WAREHOUSE, INC.
                              AMENDED AND RESTATED
                        1998 EMPLOYEE STOCK PURCHASE PLAN
                            (Full title of the plan)

                             -----------------------

                                YALE T. DOLGINOW
                      PRESIDENT AND CHIEF EXECUTIVE OFFICER
                              PAPER WAREHOUSE, INC.
                            7630 EXCELSIOR BOULEVARD
                              MINNEAPOLIS, MN 55426
                                 (952) 936-1000
                      (Name, address and telephone number,
                   including area code, of agent for service)

                              --------------------
CALCULATION OF REGISTRATION FEE
===================================================================================================================
                                                                            PROPOSED MAXIMUM
  TITLE OF SECURITIES TO     AMOUNT TO BE     PROPOSED MAXIMUM OFFERING    AGGREGATE OFFERING       AMOUNT OF
       BE REGISTERED        REGISTERED (1)        PRICE PER UNIT (2)             PRICE           REGISTRATION FEE
-------------------------------------------------------------------------------------------------------------------
Common Stock, $.01 par
 value per share                 150,000                 $.94                   $141,000               $37
===================================================================================================================
(1)  In addition, pursuant to Rule 416(c) under the Securities Act of 1933,
     as amended, this Registration Statement also covers an
     indeterminate number of additional shares that may be offered and
     sold as a result of anti-dilution provisions described in the
     Amended and Restated 1998 Employee Stock Purchase Plan.

(2)  Estimated pursuant to Rule 457(h) under the Securities Act solely for
     the purpose of calculating the amount of the registration fee as
     follows: (i) with respect to options to purchase shares previously
     granted under the plan, on the basis of the weighted average exercise
     price of such option grants, and (ii) with respect to options to be
     granted under the plan, on the basis of the average between the high and
     low reported sales prices of the Registrant's common stock on April 25,
     2000, on the over-the-counter market, as reported by the Nasdaq National
     Market.
PART I

                              INFORMATION REQUIRED
                         IN THE SECTION 10(a) PROSPECTUS

         The documents containing the information specified in Part I of Form
S-8 have been or will be sent or given to participants as specified by Rule
428(b)(1) under the Securities Act.

                                     PART II

                              INFORMATION REQUIRED
                          IN THE REGISTRATION STATEMENT

ITEM 3.  INCORPORATION OF DOCUMENTS BY REFERENCE.

         The following documents filed by Paper Warehouse, Inc. (File No.
0-23389) with the Securities and Exchange Commission are incorporated by
reference in this Registration Statement:

         (1) Paper Warehouse's latest Annual Report on Form 10-K for the fiscal
year ended January 28, 2000;

         (2) All other reports filed by Paper Warehouse pursuant to Sections
13(a) or 15(d) of the Securities Exchange Act of 1934 since January 28, 2000;
and

         (3) The description of Paper Warehouse's common stock contained in its
Registration Statement on Form 8-A filed with the Commission on November 18,
1997 under the Exchange Act, including any amendments or reports filed for the
purpose of updating such description.

         All documents filed by Paper Warehouse with the Commission pursuant to
Sections 13(a), 13(c), 14 and 15(d) of the Exchange Act after the date of this
Registration Statement and prior to the filing of a post-effective amendment
which indicates that all securities offered pursuant to this Registration
Statement have been sold or that deregisters all securities then remaining
unsold, shall be deemed to be incorporated by reference in this Registration
Statement and to be a part hereof from the date of filing of such documents.

ITEM 4.  DESCRIPTION OF SECURITIES.

         Not applicable.

ITEM 5.  INTERESTS OF NAMED EXPERTS AND COUNSEL.

         The validity of the securities that may be offered under the Paper
Warehouse, Inc. Amended and Restated 1998 Employee Stock Purchase Plan will be
passed upon for Paper Warehouse by Oppenheimer Wolff & Donnelly LLP,
Minneapolis, Minnesota.

ITEM 6.  INDEMNIFICATION OF DIRECTORS AND OFFICERS.

         Paper Warehouse's Articles of Incorporation limit the liability of its
directors to the fullest extent permitted by the Minnesota Business Corporation
Act. Specifically, directors of Paper Warehouse will

                                       1
not be personally liable for monetary damages for breach of fiduciary duty as
directors, except liability for (i) any breach of the duty of loyalty to Paper
Warehouse or its shareholders, (ii) acts or omissions not in good faith or that
involve intentional misconduct or a knowing violation of law, (iii) dividends or
other distributions of corporate assets that are in contravention of certain
statutory or contractual restrictions, (iv) violations of certain Minnesota
securities laws, or (v) any transaction from which the director derives an
improper personal benefit. Liability under federal securities law is not limited
by Paper Warehouse's Articles of Incorporation.

         Minnesota Statutes, Section 302A.521 provides that a Minnesota business
corporation shall indemnify any director, officer, employee or agent of the
corporation made or threatened to be made a party to a proceeding, by reason of
the former or present official capacity (as defined) of the person, against
judgments, penalties, fines, settlements and reasonable expenses incurred by the
person in connection with the proceeding if certain statutory standards are met.
"Proceeding" means a threatened, pending or completed civil, criminal,
administrative, arbitration or investigative proceeding, including one by or in
the right of the corporation. Section 302A.521 contains detailed terms regarding
such right of indemnification and reference is made thereto for a complete
statement of such indemnification rights. Paper Warehouse's Articles of
Incorporation and Bylaws also require Paper Warehouse to provide indemnification
to the fullest extent of the Minnesota indemnification statute.

         Paper Warehouse also maintains a directors and officers insurance
policy pursuant to which directors and officers of Paper Warehouse are insured
against liability for certain actions in their capacity as directors and
officers.

ITEM 7.  EXEMPTIONS FROM REGISTRATION CLAIMED.

         Not applicable. No securities are to be reoffered or resold pursuant to
this Registration Statement.

ITEM 8.  EXHIBITS.

EXHIBIT NO.

5.1       Opinion of Oppenheimer Wolff & Donnelly LLP (filed herewith).

23.1      Consent of  Grant Thornton LLP (filed herewith).

23.2      Consent of KPMG LLP (filed herewith).

23.3      Consent of Oppenheimer Wolff & Donnelly LLP (included in Exhibit 5.1).

24.1      Power of Attorney (included on page 6 of this Registration Statement).

ITEM 9.  UNDERTAKINGS.

     (a) The undersigned Registrant hereby undertakes:

              (1)     To file, during any period in which offers or sales are
                      being made, a post-effective amendment to this
                      Registration Statement:

                      (i)      To include any prospectus required by Section
                               10(a)(3) of the Securities Act;

                                       2
(ii)      To reflect in the prospectus any facts or events
                                arising after the effective date of this
                                Registration Statement (or the most recent
                                post-effective amendment hereof) which,
                                individually or in the aggregate, represent a
                                fundamental change in the information set forth
                                in this Registration Statement. Notwithstanding
                                the foregoing, any increase or decrease in
                                volume of securities offered (if the total
                                dollar value of securities offered would not
                                exceed that which was registered) and any
                                deviation from the low or high end of the
                                estimated maximum offering range may be
                                reflected in the form of prospectus filed with
                                the Commission pursuant to Rule 424(b) under the
                                Securities Act if, in the aggregate, the changes
                                in volume and price represent no more than a 20%
                                change in the maximum aggregate offering price
                                set forth in the "Calculation of Registration
                                Fee" table in the effective Registration
                                Statement;

                      (iii)    To include any material information with respect
                               to the plan of distribution not previously
                               disclosed in the Registration Statement or any
                               material change to such information in this
                               Registration Statement.

                      PROVIDED, HOWEVER, that paragraphs (a)(1)(i) and
                      (a)(1)(ii) above do not apply if the information required
                      to be included in a post-effective amendment by those
                      paragraphs is contained in periodic reports filed with or
                      furnished to the Commission by the Registrant pursuant to
                      Section 13 or Section 15(d) of the Exchange Act that are
                      incorporated by reference in this Registration Statement.

              (2)     That, for the purpose of determining any liability under
                      the Securities Act, each such post-effective amendment
                      shall be deemed to be a new registration statement
                      relating to the securities offered therein, and the
                      offering of such securities at that time shall be deemed
                      to be the initial bona fide offering thereof.

              (3)     To remove from registration by means of a post-effective
                      amendment any of the securities being registered which
                      remain unsold at the termination of the offering.

     (b)      The undersigned Registrant hereby undertakes that, for purposes of
              determining any liability under the Securities Act, each filing of
              the Registrant's annual report pursuant to Section 13(a) or
              Section 15(d) of the Exchange Act (and where applicable, each
              filing of an employee benefit plan's annual report pursuant to
              Section 15(d) of the Exchange Act) that is incorporated by
              reference in this Registration Statement shall be deemed to be a
              new registration statement relating to the securities offered
              therein, and the offering of such securities at that time shall be
              deemed to be the initial bona fide offering thereof.

     (c)      Insofar as indemnification for liabilities arising under the
              Securities Act may be permitted to directors, officers and
              controlling persons of the Registrant pursuant to the foregoing
              provisions, or otherwise, the Registrant has been advised that in
              the opinion of the Commission such indemnification is against
              public policy as expressed in the Securities Act, and is
              therefore, unenforceable. In the event that a claim for
              indemnification against such liabilities (other than the payment
              by the Registrant of expenses incurred or paid by a director,
              officer or controlling person of the Registrant in the successful
              defense of any action, suit or proceeding) is asserted by such
              director, officer or controlling person in connection with the
              securities being registered, the Registrant will, unless in the
              opinion of its counsel the matter has been settled by controlling
              precedent, submit to a court of appropriate

                                       3
jurisdiction the question whether such indemnification by it is
              against public policy as expressed in the Securities Act and will
              be governed by the final adjudication of such issue.

                                       4
SIGNATURES

     Pursuant to the requirements of the Securities Act of 1933, the Registrant
certifies that it has reasonable grounds to believe that it meets all of the
requirements for filing on Form S-8 and has duly caused this Registration
Statement to be signed on its behalf by the undersigned, thereunto duly
authorized, in the City of Minneapolis, State of Minnesota, on May 1, 2000.

                            PAPER WAREHOUSE, INC.

                               By: /s/ Yale T. Dolginow
                                  ----------------------------------------------
                                   Yale T. Dolginow
                                   President and Chief Executive Officer
                                   (principal executive officer)

                               By: /s/ Cheryl W. Newell
                                  ----------------------------------------------
                                   Cheryl W. Newell
                                   Vice President and Chief Financial Officer
                                   (principal financial  officer)

                               By: /s/ Diana G. Purcel
                                  ----------------------------------------------
                                   Diana G. Purcel
                                   Controller
                                   (principal accounting officer)

                                       5
POWER OF ATTORNEY

     Each person whose signature appears below constitutes and appoints Yale T.
Dolginow and Cheryl W. Newell, and each of them, his or her true and lawful
attorney-in-fact and agent with full powers of substitution and resubstitution,
for and in his or her name, place and stead, in any and all capacities, to sign
any or all amendments (including post-effective amendments) to this Registration
Statement, and to file the same, with all exhibits thereto, and other documents
in connection therewith, with the Securities and Exchange Commission, granting
unto said attorney-in-fact and agent full power and authority to do and perform
each and every act and thing requisite or necessary to be done in and about the
premises, as fully to all intents and purposes as he or she might or could do in
person, hereby ratifying and confirming all that said attorney-in-fact and agent
or his or her substitute or substitutes, may lawfully do or cause to be done by
virtue thereof.

     Pursuant to the requirements of the Securities Act of 1933, this
Registration Statement has been signed on May 1, 2000 by the following persons
in the capacities indicated.
SIGNATURE                            TITLE
---------                            -----
/s/ Yale T. Dolginow
----------------------------         President and Chief Executive Officer
Yale T. Dolginow                     and Director, Chairman of the Board

/s/ Arthur H. Cobb
----------------------------         Director
Arthur H. Cobb

/s/ Diane C. Dolginow
----------------------------         Secretary and Director
Diane C. Dolginow

/s/ Marvin W. Goldstein
----------------------------         Director
Marvin W. Goldstein

/s/ Jeffrey S. Halpern
----------------------------         Director
Jeffrey S. Halpern

/s/ Martin A. Mayer
----------------------------         Director
Martin A. Mayer

/s/ Cheryl W. Newell
----------------------------         Vice President and Chief Financial Officer
Cheryl W. Newell

/s/ Diana G. Purcel
----------------------------         Controller
Diana G. Purcel
6
INDEX TO EXHIBITS

 NO.                              ITEM                             METHOD OF FILING
 --                               ----                             ----------------
5.1       Opinion of Oppenheimer Wolff & Donnelly LLP..............Filed herewith.

23.1      Consent of  Grant Thornton LLP...........................Filed herewith

23.2      Consent of KPMG LLP......................................Filed herewith.

23.3      Consent of Oppenheimer Wolff & Donnelly LLP..............Included in Exhibit 5.1.

24.1      Power of Attorney........................................Included on page 6 of this Registration
                                                                   Statement.