EXHIBIT 5.1
                  [Oppenheimer Wolff & Donnelly LLP Letterhead]

August 9, 2000

Paper Warehouse, Inc.
7630 Excelsior Boulevard
Minneapolis, MN 55426

RE:      PAPER WAREHOUSE, INC.  REGISTRATION STATEMENT ON FORM S-8

Ladies and Gentlemen:

We have acted as counsel to Paper Warehouse, Inc., a Minnesota corporation
(the "Company"), in connection with the Company's registration of offers and
sales by its current and former employees of 9,246 shares (the "Shares") of
common stock, $.01 par value per share (the "Common Stock") of the Company,
issuable under the Company's Amended and Restated 1998 Employee Stock
Purchase Plan (the "Plan"), pursuant to a Registration Statement on Form S-8
filed with the Securities and Exchange Commission on August 9, 2000 (the
"Registration Statement"). The Shares covered by the Registration Statement
consist of shares that have been issued by the Company in private placements.

In acting as counsel for the Company and arriving at the opinions expressed
below, we have examined and relied upon originals or copies, certified or
otherwise identified to our satisfaction, of such records of the Company,
agreements and other instruments, certificates of officers and representatives
of the Company, certificates of public officials and other documents as we have
deemed necessary or appropriate as a basis for the opinions expressed herein. In
connection with our examination, we have assumed the genuineness of all
signatures, the authenticity of all documents tendered to us as originals, the
legal capacity of all natural persons and the conformity to original documents
of all documents submitted to us as certified or photostatic copies.

Based on the foregoing, and subject to the qualifications and limitations stated
herein, it is our opinion that:

1. The Company had the corporate authority to issue the Shares covered by the
Registration Statement that are currently outstanding.

2. The Shares being registered for resale under the Registration Statement
have been duly authorized and are validly issued, fully paid and
non-assessable.

We express no opinion with respect to laws other than those of the State of
Minnesota and the federal laws of the United States of America, and we assume no
responsibility as to the applicability thereto, or the effect thereon, of the
laws of any other jurisdiction.

We hereby consent to the filing of this opinion as Exhibit 5.1 to the
Registration Statement and to its use as part of the Registration Statement.

Very truly yours,

OPPENHEIMER WOLFF & DONNELLY LLP

/s/ Oppenheimer Wolff & Donnelly LLP