1
 
                            SCHEDULE 14A INFORMATION
 
                   PROXY STATEMENT PURSUANT TO SECTION 14(A)
                     OF THE SECURITIES EXCHANGE ACT OF 1934
                               (AMENDMENT NO. __)
 
Filed by the Registrant                      / /
 
Filed by a Party other than the Registrant  / /
 

                                                  
Check the appropriate box:
 
/ /  Preliminary Proxy Statement                     / /  Confidential, for Use of Commission Only (as
/X/  Definitive Proxy Statement                           permitted by Rule 14a-6(e)(2))
/ /  Definitive Additional Materials
/ /  Soliciting Material Pursuant to sec.240.14a-11(c) or sec.240.14a-12

 
                           NATIONAL RECORD MART, INC.
                (NAME OF REGISTRANT AS SPECIFIED IN ITS CHARTER)
 
    (NAME OF PERSON(S) FILING PROXY STATEMENT IF OTHER THAN THE REGISTRANT)
 
Payment of Filing Fee (Check the appropriate box):
/X/  $125 per Exchange Act Rules 0-11(c)(1)(ii), 14a-6(i)(1), or 14a-6(i)(2) or
     Item 22(a)(2) of Schedule 14A
/ /  $500 per each party to the controversy pursuant to Exchange Act Rule
     14a-6(i)(3)
/ /  Fee computed on table below per Exchange Act Rules 14a-6(i)(4) and 0-11
 
     (1) Title of each class of securities to which transaction applies:
 
- ----------------------------------------------------------------------------
     (2) Aggregate number of securities to which transaction applies:
 
- ----------------------------------------------------------------------------
     (3) Per unit price or other underlying value of transaction computed
         pursuant to Exchange Act Rule 0-11 (set forth the amount on which the
         filing fee is calculated and state how it was determined):
 
- ----------------------------------------------------------------------------
     (4) Proposed maximum aggregate value of transaction:
 
- ----------------------------------------------------------------------------
     (5) Total fee paid:
 
- ----------------------------------------------------------------------------
/ /  Fee paid previously with preliminary materials.
 
/ /  Check box if any part of the fee is offset as provided by Exchange Act Rule
     0-11(a)(2) and identify the filing for which the offsetting fee was paid
     previously. Identify the previous filing by registration statement number,
     or the Form or Schedule and the date of its filing.
 
     (1) Amount Previously Paid:
     ------------------------------
 
     (2) Form, Schedule or Registration No.:
     ------------------------------
 
     (3) Filing Party:
     ------------------------------
 
     (4) Date Filed:
     ------------------------------
   2
 
                                      LOGO
 
                           NATIONAL RECORD MART, INC.
                               507 FOREST AVENUE
                          CARNEGIE, PENNSYLVANIA 15106
 
                            ------------------------
 
          NOTICE OF ANNUAL MEETING OF STOCKHOLDERS--SEPTEMBER 18, 1996
 
     Notice is hereby given of the Annual Meeting of Stockholders of National
Record Mart, Inc. (the "Company"), which will be held at One PNC Plaza, Fifth
and Wood Streets, 16th Floor, Pittsburgh, Pennsylvania 15265, at 9:30 a.m. on
Wednesday, September 18, 1996, for the following purposes:
 
          (1) To elect four directors of the Company to serve until the next
     annual meeting and until their successors are chosen and qualified;
 
          (2) To ratify the appointment of Ernst & Young as independent auditors
     of the Company for the fiscal year ending March 29, 1997; and
 
          (3) To transact such other business as may properly come before the
     Annual Meeting and any adjournments thereof.
 
     Only stockholders of record at the close of business on July 29, 1996 are
entitled to notice of and to vote at this Annual Meeting and any adjournments
thereof. A complete list of the stockholders entitled to vote shall be available
during the period of ten (10) days prior to the date of the Annual Meeting for
examination by any stockholder, for any purpose germane to the Annual Meeting
during ordinary business hours at 507 Forest Avenue, Carnegie, Pennsylvania.
 
     Your vote is important. A proxy and return envelope are enclosed for your
convenience. Please complete and return your proxy card as promptly as possible.
 
                                               By Order of the Board of
                                               Directors,
 
                                               LYNDA J. HUFFMAN
                                               Secretary
August 13, 1996
 
     IMPORTANT: YOU ARE CORDIALLY INVITED TO ATTEND THE ANNUAL MEETING IN
PERSON. WHETHER OR NOT YOU PLAN TO ATTEND THE MEETING, PLEASE COMPLETE, SIGN AND
RETURN THE ENCLOSED PROXY. A RETURN ENVELOPE REQUIRING NO POSTAGE IF MAILED IN
THE UNITED STATES IS ENCLOSED FOR YOUR CONVENIENCE. PROMPT RETURN OF THE PROXY
WILL ASSURE A QUORUM AND SAVE THE COMPANY UNNECESSARY EXPENSE. YOUR PROXY MAY BE
WITHDRAWN BY YOU AT ANY TIME BEFORE IT IS VOTED.
   3
 
August 13, 1996
 
                           NATIONAL RECORD MART, INC.
                               507 FOREST AVENUE
                          CARNEGIE, PENNSYLVANIA 15106
 
                                PROXY STATEMENT
                         ANNUAL MEETING OF STOCKHOLDERS
                               SEPTEMBER 18, 1996
 
                              GENERAL INFORMATION
 
     This Proxy Statement is furnished to the stockholders of National Record
Mart, Inc., a Delaware corporation (the "Company"), in connection with the
solicitation of proxies by the Board of Directors for use at the Annual Meeting
of Stockholders of the Company to be held on September 18, 1996 and any
adjournments thereof. A copy of the Notice of Annual Meeting of Stockholders
accompanies this Proxy Statement. It is anticipated that the mailing of this
Proxy Statement and the form of proxy will commence on August 14, 1996. The 1996
Annual Report to Stockholders (which does not form a part of the proxy
solicitation material), including the financial statements of the Company for
the fiscal year ending March 30, 1996 ("Fiscal Year 1996"), is enclosed
herewith.
 
                            SOLICITATION OF PROXIES
 
     The shares represented by any Proxy given pursuant to this solicitation
will be voted at the Annual Meeting and, if a choice is specified on the Proxy,
will be voted in accordance with such specification. In the event no choice is
specified on the Proxy, the shares represented by such Proxy will be voted FOR
the nominees for directors set forth herein and FOR the ratification of the
appointment of Ernst & Young as independent auditors. So far as is presently
known, there is no business to be transacted at the Annual Meeting other than
that referred to in the Notice of Annual Meeting of Stockholders and described
herein and it is not anticipated that other matters will be brought before the
Annual Meeting. If any other matters properly come before the Annual Meeting, or
if any of the persons named to serve as directors or as auditors should decline
or be unable to serve, the persons named in the Proxy will vote on the same in
accordance with their discretion. Shares which are present, or represented by a
proxy, at the Annual Meeting will be counted for quorum purposes regardless of
whether the holder of the shares or proxy fails to vote ("abstentions") or
whether a broker with discretionary authority fails to exercise its
discretionary authority to vote ("broker non-votes"). However, if a broker or
nominee limits on the proxy card the number of shares voted or indicates that
the shares represented by a proxy card are not voted, such "non-votes" will not
be voted and will not be counted as affirmative votes.
 
     A Proxy may be revoked by the person giving it before it is voted by (i)
delivering to the Secretary of the Company, at the address listed at the
beginning of this Proxy Statement, a written notice of revocation which must be
signed in exactly the same manner as the Proxy, (ii) filing with the Secretary
of the Company a duly executed Proxy which bears a later date or (iii)
delivering the signed, written revocation to the Inspector of Elections at the
Annual Meeting. Revocations and subsequent Proxies will be honored only if
received at the Company's offices on or before September 11, 1996 or delivered
to the Inspector of Elections at the Annual Meeting prior to the convening
thereof. Presence at the Annual Meeting alone will not revoke the Proxy.
 
                         QUORUM AND TABULATION OF VOTES
 
     The Bylaws of the Company provide that a majority of the shares of Common
Stock issued and outstanding and entitled to vote, present in person or by
proxy, shall constitute a quorum at the Annual Meeting of Stockholders of the
Company. Votes at the Annual Meeting will be tabulated by the Secretary of the
Company. Shares of Common Stock represented by a properly signed and returned
proxy are considered as present at the Annual Meeting for purposes of
determining a quorum.
 
                                        1
   4
 
                               VOTING SECURITIES
 
     The Company has only one class of voting securities, its Common Stock, par
value $.01 per share (the "Common Stock"). As of the close of business on the
record date, July 29, 1996, 5,037,916 shares of Common Stock were outstanding.
Each stockholder of record at the close of business on July 29, 1996 will be
entitled to one vote for each share of Common Stock owned on that date as to
each matter presented to the meeting.
 
                      BENEFICIAL OWNERSHIP OF COMMON STOCK
 
     The following table sets forth certain information as to the beneficial
ownership of the Common Stock by (i) each director of the Company and each
executive officer listed in the Summary Compensation Table, (ii) each person
known by the Company to be the beneficial owner of more than 5% of the Common
Stock and (iii) all directors and executive officers of the Company as a group.
The information in the table and the related footnotes pertaining to directors
and executive officers is based upon data furnished to the Company by or on
behalf of such persons. Unless otherwise indicated, each of the following
stockholders has sole voting and sole investment power with respect to the
shares beneficially owned by such stockholder.
 


                                                               SHARES BENEFICIALLY OWNED
                                                               --------------------------
      NAME AND ADDRESS                                           NUMBER           PERCENT
      ----------------                                         ----------         -------
                                                                            
      William A. Teitelbaum (1)                                 1,147,340          22.77%
      Theresa Carlise (2)                                           4,000              *
      Irwin B. Goldstein (2)                                        4,900              *
      Samuel S. Zacharias (2) (3)                                  98,960           1.96%
      Michele A. Teitelbaum (4)                                   309,800           6.15%
      16 Carlisle Drive
      Old Brookville, NY 11545
      All executive officers and directors as a group           1,269,450          25.20%
        (6 persons)

 
- ---------
 
* Less than 1%
 
(1) Address is 16 Carlisle Drive, Old Brookville, New York 11545. Includes
    181,042 shares held by the National Record Mart, Inc. Profit Sharing Plan
    and Trust of which Mr. Teitelbaum is trustee and as to which shares Mr.
    Teitelbaum has voting and investment power. Also includes 28,500 shares held
    by Remsen Partners, Ltd., an affiliate of Mr. Teitelbaum. Excludes 309,800
    shares owned by Mr. Teitelbaum's wife as to which shares Mr. Teitelbaum
    disclaims beneficial ownership.
 
(2) Address is c/o the Company, 507 Forest Avenue, Carnegie, Pennsylvania 15106.
 
(3) Represents shares held by REALSEARCH AG and Three Rivers Energy Corporation,
    affiliates of Mr. Zacharias.
 
(4) Does not include shares held by her husband, William A. Teitelbaum, as to
    which shares Mrs. Teitelbaum disclaims beneficial ownership.
 
                              PROXY PROPOSAL NO. 1
 
                             ELECTION OF DIRECTORS
 
     At the Annual Meeting, four directors will be elected to hold office
(subject to the Company's Bylaws) until the next Annual Meeting of Stockholders
and until his or her respective successor has been elected and qualified.
Directors of the Company will be elected by a plurality vote of the outstanding
shares of Common Stock present and entitled to vote at the Annual Meeting.
 
     If any nominee listed below should become unavailable as a candidate for
any reason, which management does not anticipate, the Proxy will be voted for
any substitute nominee or nominees who may be selected by
 
                                        2
   5
 
the Board of Directors prior to or at the Annual Meeting or, if no substitute is
selected by the Board of Directors, for a motion to reduce the number of
directors to the number of nominees available. The information concerning the
nominees has been furnished by them to the Company. Each nominee has consented
to being named a nominee for director and has agreed to serve if elected. THE
BOARD OF DIRECTORS RECOMMENDS THAT THE STOCKHOLDERS VOTE FOR THE ELECTION OF THE
FOUR PERSONS NOMINATED TO THE BOARD OF DIRECTORS.
 
     The following table sets forth certain information concerning the nominees,
all of whom are presently directors of the Company.
 


                                          DIRECTOR
    NAME, AGE                              SINCE                    POSITION
    ---------                             --------                  --------    
                                                 
    William A. Teitelbaum, 46               1986       Chairman, President, Chief
                                                       Executive Officer and Director
    Theresa Carlise, 37                     1993       Senior Vice President, Chief
                                                       Financial Officer and Director
    Samuel S. Zacharias, 53                 1993       Director
    Irwin B. Goldstein, 67                  1993       Director

 
     Mr. Teitelbaum has served as Chairman of the Company since 1986 and has
served as President and Chief Executive Officer since 1991. He also served as
Vice President and Treasurer from 1986 to 1991. From 1980 to 1985, he was a
partner of Bear Stearns & Co. In addition, since 1985 Mr. Teitelbaum has been
the sole shareholder and Chairman of Remsen Partners, Ltd., a New York
investment firm.
 
     Ms. Carlise joined the Company in July 1986 as a financial systems
consultant in connection with the establishment of an automated accounting
system and subsequently became Controller of the Company in 1987. She served as
Vice President of Finance of the Company from April 1990 to April 1993, when she
became Senior Vice President, Chief Financial Officer and a director.
 
     Mr. Zacharias has been President and a senior partner of Gateway Financial
Group, Inc., an insurance consulting and merchant banking firm, since 1983. Mr.
Zacharias also has served as President and a director of Realsearch
International, Ltd., an investment banking firm, since 1979. Mr. Zacharias has
served as a director of the Company since January 1993.
 
     Mr. Goldstein was Senior Vice President--Credit for Warner Elektra Atlantic
Corp. from 1985 until his retirement in 1992. From 1977 to 1985, Mr. Goldstein
served in various positions at Warner Elektra Atlantic Corp., including Vice
President and Director of Credit. Mr. Goldstein has served as a director of the
Company since September 1993.
 
BOARD OF DIRECTORS AND COMMITTEES OF THE BOARD
 
     In Fiscal Year 1996, the Board of Directors met once and also acted on
three occasions by unanimous written consent. In Fiscal Year 1996, none of the
directors attended fewer than 75% of aggregate of the total number of meetings
of the Board of Directors and the total number of meetings held by all
committees of the Board upon which such director served.
 
     The Board of Directors of the Company has established an Audit Committee
and a Compensation and Stock Option Committee. The Audit Committee, comprised of
Messrs. Goldstein and Zacharias, oversees actions taken by the Company's
independent auditors and reviews the Company's internal controls. The
Compensation and Stock Option Committee, comprised of Mr. Zacharias, reviews the
compensation of the Company's officers and administers the Company's 1993 Stock
Option Plan and 1993 Non-Employee Director Stock Option Plan. The Audit
Committee met twice in Fiscal Year 1996 and the Compensation Committee met once.
 
                                        3
   6
 
     Compensation Committee Interlocks and Insider Participation. As stated
above, the Compensation and Stock Option Committee consists of Mr. Zacharias.
During Fiscal Year 1996, no executive officer served on a compensation committee
(or other board committee performing equivalent functions) or board of directors
of an entity related to any member of the Board of Directors.
 
     Cash Compensation. Directors who are employees of the Company do not
receive a retainer or fees for attending meetings of the Board of Directors or
meetings of committees of the Board. Non-employee directors of the Company
receive as compensation for their services to the Company, in addition to
reimbursement for out-of-pocket expenses in connection with attending Board
meetings, an annual fee of $5,000, payable in quarterly installments and a
meeting fee of $1,000 for each regularly scheduled meeting day and $500 for any
committee meeting attended.
 
     Non-Employee Director Stock Option Plan. In May 1993, the Board of
Directors adopted the National Record Mart, Inc. 1993 Non-Employee Director
Stock Option Plan (the "Directors Plan"), which was approved by the Stockholders
of the Company on June 3, 1993. The Directors Plan provides for the grant of
options to purchase Common Stock to those directors who are neither employees
nor former employees of the Company.
 
     Options to purchase up to 15,000 shares of Common Stock may be granted
under the Directors Plan. Shares issued upon exercise of options granted under
the Directors Plan may be authorized but unissued shares, shares repurchased and
held in treasury by the Company or a combination thereof. Each option vests over
a five-year period with one-fifth of the option shares vesting on each of the
first through fifth anniversaries of the date of the grant. The exercise price
of options granted under the Directors Plan is the fair market value (as
determined pursuant to the Directors Plan) of the Common Stock on the date of
grant of the option (except that, in the case of the initial grant of options in
fiscal 1994, the exercise price is $7.50 per share). Options granted under the
Directors Plan may be exercised by a participant by giving written notice to the
Company and by paying the exercise price in cash or by surrendering other shares
of Common Stock with a market value equal to the exercise price.
 
     The Directors Plan will terminate on the tenth anniversary of its effective
date, subject to earlier termination by the Board of Directors. The Board of
Directors has the authority to amend or terminate the Directors Plan at any time
without approval, except for certain amendments which require stockholder
approval. Amendments requiring stockholder approval include amendments which
would materially increase the benefits accruing to participants, materially
increase the number of securities which may be issued under the Directors Plan
or materially modify the requirements as to eligibility for participation in the
Directors Plan. In addition, no action by the Board of Directors or the
Stockholders with respect to the Directors Plan may alter or impair any option
previously granted without the participant's consent.
 
     Vested options granted under the Directors Plan must be exercised within
ten years from the date of grant. In the event of a participant's termination of
membership on the Board of Directors, the participant will have three months to
exercise any vested options then outstanding. In the case of termination of
membership on the Board of Directors for disability or death of the participant,
the participant or his or her estate or beneficiary (as applicable) will have
twelve months to exercise any vested options. In the event of a "change in
control" (as defined in the Directors Plan) involving the Company, all options
then outstanding, including options which have not yet vested, will be deemed to
vest immediately upon occurrence of the event constituting the change in
control.
 
     As of March 30, 1996, the two non-employee directors of the Company as a
group had received options to purchase a total of 10,000 shares. Such options
had no aggregate value as measured by the differences between the closing price
of the Common Stock on the NASDAQ National Market System as of March 30, 1996
($1.125 per share) and the exercise price of the options ($7.50 per share).
Executive officers, directors who are employed by the Company and other
employees of the Company are not eligible to receive any grant of options under
the Directors Plan.
 
                                        4
   7
 
                      EXECUTIVE OFFICERS AND COMPENSATION
 
     The Company's executive officers, other than Mr. Teitelbaum and Ms.
Carlise, are identified below.
 
     Larry Mundorf, age 48, joined the Company in January of 1996 as Executive
Vice President and Chief Operating Officer. Mr. Mundorf spent 23 years with
Camelot Music, Inc., rising through the ranks to Senior Vice President of
Operations and Director. In 1991, he joined manufacturer Alpha Enterprises,
located in Canton, Ohio, a supplier to the music and video industry, as Vice
President of Marketing until 1995.
 
     George Balicky, age 46, is Vice President--Merchandising. Mr. Balicky has
served the Company in various capacities since 1970, including Director of
Advertising, Director of Store Operations and Vice President of Merchandising.
He is a member of the Retailers Advisory Board of the National Association of
Recording Merchandisers. He has been Vice President--Merchandising since 1985.
 
COMPENSATION OF EXECUTIVE OFFICERS
 
     The following table sets forth information regarding the annual and
long-term compensation paid by the Company during Fiscal Year 1996, 1995 and
1994 to the Chairman, President and Chief Executive Officer of the Company.
There was no other executive officer of the Company whose total annual
compensation during Fiscal Year 1996 was at least $100,000.
 
                           SUMMARY COMPENSATION TABLE
 


                                                                                     LONG-TERM
                                                                                   COMPENSATION
                                                ANNUAL COMPENSATION                   AWARDS
                                           ------------------------------         ---------------
                                FISCAL                     OTHER ANNUAL               OPTIONS
NAME AND PRINCIPAL POSITION      YEAR       SALARY        COMPENSATION(1)         (NO. OF SHARES)
- ---------------------------     ------     --------       ---------------         ---------------
                                                                      
William A. Teitelbaum            1996      $225,000           $ 4,840                      --
  Chairman, President, Chief     1995      $225,000           $ 4,190                      --
  Executive Officer and          1994      $225,000                --                 200,000
     Director

 
- ---------
 
(1) Amount represents premiums paid for by the Company for insurance, pursuant
    to the terms of Mr. Teitelbaum's employment agreement, discussed below in
    "Certain Relationships and Related Transactions." Except as otherwise noted,
    no other compensation was paid during Fiscal Year 1996 (except for
    perquisites and other personal benefits, the amount of which was less than
    10% of the officer's total compensation).
 
OPTION EXERCISES IN FISCAL YEAR 1996 AND 1996 FISCAL YEAR-END VALUES
 
     The following table sets forth as to the person named in the Summary
Compensation Table information with respect to (i) the number of shares received
upon the exercise of options, (ii) the aggregate dollar value realized upon
exercise, (iii) the total number of shares underlying unexercised options held
at the end of Fiscal Year 1996 and (iv) the aggregate dollar value of
in-the-money unexercised options held at the end of Fiscal Year 1996.
 
                AGGREGATED OPTION EXERCISES IN FISCAL YEAR 1996
                            AND FY-END OPTION VALUES
 


                                                                                             VALUE OF
                                                            NUMBER OF SECURITIES            UNEXERCISED
                                                                UNDERLYING                 IN-THE-MONEY
                                                               UNEXERCISED                  OPTIONS AT
                           SHARES                            OPTIONS AT FISCAL            FISCAL YEAR-END
                         ACQUIRED ON      VALUE                YEAR-END (#)                   ($)(1)
NAME                    EXERCISE (#)   REALIZED ($)     (EXERCISABLE/UNEXERCISABLE) (EXERCISABLE/UNEXERCISABLE)
- ----                    -------------  ------------     --------------------------- ---------------------------
                                                                           
William A. Teitelbaum         0             $0               20,000/180,000            $20,500/$184,500

 
- ---------
 
(1) Based on the closing price per share of the Common Stock on the NASDAQ
    National Market System as of March 30, 1996, minus the exercise price per
    share, multiplied by the number of shares obtainable upon exercise of such
    options.
 
                                        5
   8
 
REPORT OF THE COMPENSATION COMMITTEE ON EXECUTIVE COMPENSATION
 
     Notwithstanding anything to the contrary set forth in any of the Company's
previous filings under the Securities Act of 1933, as amended, or the Securities
Exchange Act of 1934, as amended, that might incorporate future filings,
including this Proxy Statement in whole or in part, the following report and the
Stock Performance Graph on page 8 shall not be incorporated by reference into
any such filings.
 
                      REPORT OF THE COMPENSATION COMMITTEE
                           OF THE BOARD OF DIRECTORS
 
To: The Board of Directors
 
     The Compensation Committee of the Board of Directors of National Record
Mart, Inc. (the "Company") is responsible for establishing the policies and
programs which determine the compensation of the Company's Chief Executive
Officer and other executive officers. The Committee reviews with the Board, in
detail, all aspects of compensation for such officers. The Committee is also
responsible for administering and granting stock options pursuant to the
Company's 1993 Stock Option Plan. No member of the Committee is a former or
current officer or employee of the Company.
 
     Base Salaries and Bonuses. Except as provided below, the base salaries and
bonuses of the executive officers for each fiscal year are established by the
Board of Directors upon recommendation of the Committee. Base salary is
determined at the beginning of each fiscal year and bonuses, if any, are awarded
after the financial results for the fiscal year have become available.
 
     Base salary depends primarily on the office and responsibilities of the
executive officer and is reviewed annually. Increases are normally affected by
the Company's financial performance. Mr. Teitelbaum's base salary for the 1996
fiscal year was specified under his five year employment agreement with the
Company, dated April 1, 1993, described in the Company's proxy statement. That
agreement establishes Mr. Teitelbaum's base salary at $225,000 per year. Two
other executive officers entered into employment agreements with the Company in
calendar year 1996.
 
     As to bonuses, it is a basic philosophy of the Committee that executive
officers should have a meaningful portion of their total compensation tied to
the profitability of the Company. Accordingly, financial results for the fiscal
year in question are a primary consideration, but other factors have
significance as well including the individual performance of each officer. Under
the terms of his employment agreement, Mr. Teitelbaum is entitled to bonus
compensation in an amount equal to 4% of the increase (if any) in the Company's
"pre-tax operating income" over the prior year. No such bonus was paid in fiscal
1996 or 1995.
 
     Stock Options. Stock options are granted by the Committee pursuant to the
Company's 1993 Stock Option Plan and are the principal form of long-term
compensation presently received by the Company's executive officers. The
Committee views stock options as particularly beneficial long-term incentives
because such options aid in tying the interests of the executives with those of
the stockholders. The decisions of the Committee with respect to stock options
are based upon each individual's job level and performance.
 
                                        Compensation Committee
                                        Samuel S. Zacharias
                                        June 21, 1996
 
                                        6
   9
 
                 CERTAIN RELATIONSHIPS AND RELATED TRANSACTIONS
 
     Teitelbaum Loans. As of June 14, 1996, Mr. Teitelbaum and an affiliated
company were indebted to the Company for approximately $346,162; the maximum
amount of such indebtedness outstanding during Fiscal Year 1996 was
approximately $394,682. The indebtedness consists primarily of a loan made to
Mr. Teitelbaum and reimbursement due to the Company from the affiliated company
for certain insurance premiums, each bearing interest at prime plus 1 1/2%, and
a federal withholding tax payment required to be remitted by the Company in 1995
on certain compensation paid to Mr. Teitelbaum in prior years, as to which
compensation Mr. Teitelbaum had previously paid the applicable tax, repayable
upon Mr. Teitelbaum's receipt of a refund for such tax.
 
     Employment Agreement. William A. Teitelbaum has an employment agreement
with the Company for an initial term of five years commencing on April 1, 1993.
Such term is automatically renewed for the third calendar year thereafter on
April 1, 1996 and each anniversary of such date unless either party elects to
terminate such automatic renewal. The agreement provides for an annual base
salary of $225,000 commencing on June 27, 1993, with annual cost of living
increases or other merit increases approved by the Board of Directors plus a
bonus equal to four percent of the increase in the Company's pre-tax operating
income from the prior fiscal year, subject to a maximum bonus equal to his base
salary. Pursuant to the agreement, the Company has purchased $5.0 million of
life insurance for which Mr. Teitelbaum may designate the beneficiary. The
agreement prohibits Mr. Teitelbaum from competing with the Company during his
employment and for a period equal to the greater of (i) two years after his
termination for proper cause or (ii) the period of time during which he is
receiving payments from the Company pursuant to the agreement. The agreement
requires the Company to pay Mr. Teitelbaum an amount equal to 2.99 times his
"base amount" (as defined by the Internal Revenue Code) if, following a change
in control of the Company, the agreement is terminated by Mr. Teitelbaum,
provided the Company achieves certain minimum stockholder investment returns, by
Mr. Teitelbaum. Under his employment agreement, Mr. Teitelbaum is entitled to
fringe benefits including vacation and health insurance pursuant to the
compensation policies and practices of the Company, as well as an automobile and
reimbursement for expenses reasonably incurred by Mr. Teitelbaum in connection
with the performance of his services to the Company. Mr. Teitelbaum is also
entitled to such supplementary retirement benefits, if any, as may be provided
by any plan or plans hereafter established by the Company. The agreement
provides that Mr. Teitelbaum will devote a substantial majority of his working
time as a full-time officer of the Company, although it permits him to engage in
non-competitive business activities.
 
     The Company believes that each of the transactions and agreements above
contains terms no less favorable to the Company than could be obtained from
unaffiliated third parties on an arms' length basis.
 
                                        7
   10
 
STOCK PERFORMANCE GRAPH
 
     The following graph compares the monthly cumulative total stockholder
return on the Company's Common Stock during the period from August 5, 1993 (the
date on which the Company's stock first traded on the NASDAQ National Market
System) to March 30, 1996 with the monthly cumulative total stockholder return
during such period on stocks included in (a) the NASDAQ Composite Index and (b)
an index of peer issuers in the Company's industry (the "Peer Group Index") made
up of the Company, Spec's Music, Inc., Trans World Entertainment Corp., and
Musicland Stores Corp., weighted for market capitalization as of the beginning
of the period presented. The information presented in the graph assumes that
$100 was invested on August 5, 1993 in the Company's stock, the NASDAQ Composite
Index and the Peer Group Index and that all dividends were reinvested.
 
                           32-MONTH CUMULATIVE RETURN
 


                                  NATIONAL           NASDAQ
      MEASUREMENT PERIOD         RECORD MART,       COMPOSITE
    (FISCAL YEAR COVERED)            INC.            INDEX        PEER GROUP
                                                        
AUG                                 100             100             100
SEP                               83.31          102.96          106.39
OCT                               93.31          105.29          128.25
NOV                               94.11          102.15          123.16
DEC                               97.44          105.00          142.15
JAN 94                            83.31          108.18          122.45
FEB                               69.98          107.20          116.98
MAR                               73.32          100.60          122.30
APR                               63.32           99.30          119.17
MAY                               59.99           99.54          106.66
JUN                               53.32           95.92           97.73
JUL                               68.32           97.89           99.06
AUG                               53.32          104.13          104.00
SEP                               66.65          103.86           94.63
OCT                               66.65          105.87           91.67
NOV                               53.32          102.34           82.57
DEC                               46.66          102.66           65.25
JAN 95                            41.66          103.23           53.98
FEB                               39.37          108.96           62.58
MAR                               34.99          112.13           57.63
APR                               29.99          117.50           57.09
MAY                               29.99          120.54           55.90
JUN                               31.66          130.33           57.99
JUL                               33.33          139.89           57.73
AUG                               31.66          142.72           54.56
SEP                               36.66          146.01           51.18
OCT                               31.66          145.18           39.99
NOV                               21.66          148.57           36.53
DEC                               12.70          147.74           25.36
JAN 96                            16.66          148.41           22.23
FEB                               26.66          154.07           20.71
MAR                               15.00          154.59           26.40

 
                                        8
   11
 
                              PROXY PROPOSAL NO. 2
 
              RATIFICATION OF APPOINTMENT OF INDEPENDENT AUDITORS
 
     The Company's independent auditors for Fiscal Year 1996 were Ernst & Young,
independent public accountants. On July 31, 1996, the Board of Directors
appointed Ernst & Young to audit the books and records of the Company for the
fiscal year ended March 29, 1997. Although the submission of this matter to the
stockholders is not required by law, the Board of Directors desires to obtain
the stockholders' ratification of such appointment. A resolution ratifying the
appointment will be offered at the Annual Meeting. If the resolution is not
adopted, the adverse vote will be considered as direction to the Board to select
other auditors for the following year.
 
     It is expected that a representative of Ernst & Young will be present at
the Annual Meeting to respond to appropriate questions and to make a statement
if the representative so desires.
 
     Ratification requires the affirmative vote by holders of at least a
majority of the shares voting on such matter. THE BOARD OF DIRECTORS RECOMMENDS
THAT THE STOCKHOLDERS VOTE FOR THE APPOINTMENT OF ERNST & YOUNG AS THE COMPANY'S
INDEPENDENT AUDITORS FOR FISCAL YEAR 1997.
 
                            EXPENSES OF SOLICITATION
 
     The costs of this solicitation have been, or will be, borne by the Company.
In addition to the use of the mails, proxies may be solicited by the Company's
directors, officers and employees, without extra compensation, by personal
interview, telephone and telegram. Arrangements will be made with brokerage
houses and other custodians, nominees and fiduciaries for the forwarding of
solicitation material and annual reports to the beneficial owners of stock held
of record by such persons, and the Company will reimburse them for reasonable
out-of-pocket and clerical expenses incurred by them in connection therewith.
 
                           ANNUAL REPORT ON FORM 10-K
 
     UPON WRITTEN REQUEST OF ANY STOCKHOLDER SOLICITED HEREBY, THE COMPANY WILL
PROVIDE WITHOUT CHARGE A COPY OF THE COMPANY'S ANNUAL REPORT ON FORM 10-K FOR
THE FISCAL YEAR ENDED MARCH 30, 1996. REQUESTS SHOULD BE DIRECTED TO LYNDA J.
HUFFMAN, 507 FOREST AVENUE, CARNEGIE, PENNSYLVANIA 15106. ANY BENEFICIAL OWNER
SHOULD INCLUDE A GOOD FAITH REPRESENTATION THAT AS OF THE RECORD DATE HE OR SHE
IS A BENEFICIAL OWNER OF SECURITIES ENTITLED TO VOTE.
 
                         STOCKHOLDER PROPOSALS FOR 1997
 
     In order for any stockholder proposal to be considered for inclusion in the
Company's Proxy Statement and form of Proxy relating to the Annual Meeting of
Stockholders to be held in 1997, the same must be received by the Company at its
principal executive offices no later than April 16, 1997.
 
                                        By Order of the Board of Directors,

                                             /s/  LYNDA J. HUFFMAN
                                            
                                               Lynda J. Huffman
                                                    Secretary
 
                                        9
   12
                           NATIONAL RECORD MART, INC.
                  PROXY FOR THE ANNUAL MEETING OF STOCKHOLDERS
                      SOLICITED BY THE BOARD OF DIRECTORS

One PNC Plaza, Fifth and Wood Streets, 16th Floor, Pittsburgh, Pennsylvania
             WEDNESDAY, SEPTEMBER 18, 1996 - 9:30 a.m. (LOCAL TIME)

The undersigned stockholder of NATIONAL RECORD MART, INC. (the "Company") does 
hereby appoint William A. Teitelbaum and Theresa Carlise, or either of them 
acting individually, with full power of substitution, as proxies of the 
undersigned to vote at the Annual Meeting of Stockholders of the Company, to be 
held September 18, 1996 (the "Annual Meeting"), and at all adjournments 
thereof, all the shares of Common Stock of the Company which the undersigned 
may be entitled to vote, on the matters set out on the reverse side of this 
card and described in the Proxy Statement and, in their discretion, on any 
business which may properly come before the Annual Meeting.

The undersigned stockholder hereby also revokes all previous proxies for the 
Annual Meeting and acknowledges receipt of the Notice of Annual Meeting of 
Stockholders and Proxy Statement, both dated August 13, 1996, and the Annual 
Report to Stockholders for 1996.

You are urged to promptly return this proxy in the enclosed envelope whether or 
not you expect to attend the Annual Meeting in person so that your shares may 
be voted in accordance with your wishes and in order that the presence of a 
quorum may be assured at the Meeting. 

The shares represented by this proxy will be voted as directed by the 
stockholder. If this proxy is executed but no direction is given, such shares 
will be voted "FOR" Items 1 and 2.


                (Continued and to be signed on the reverse side)



                                                                                          

                                                                                                    PLEASE MARK
                                                                                                     YOUR VOTES    [X]
                                                                                                      AS THIS


ITEM 1-Election of the following four Directors:                                  ITEM 2-Ratification of the appointment
William A. Teitelbaum, Theresa Carlise,                                           of Ernst & Young as independent auditors 
Samuel S. Zacharias and Irwin B. Goldstein. A vote                                of the Company for the fiscal year ending 
FOR includes discretionary authority to vote for a                                March 29, 1997.
substituted nominee if any of the nominees listed                                 
becomes unable to serve or for good cause will not serve.                       

FOR All Nominees                     WITHHOLD                       (to withhold authority to vote      FOR    AGAINST    ABSTAIN
(except as shown                     AUTHORITY                       for one or more nominees, print    [  ]     [  ]       [  ]
to the right)                 to Vote for All Nominees             such nominee's or nominees' 
  [  ]                                  [  ]                         name(s) on the line below).


                                                                            Please date and sign exactly as your name appears
                                                                            hereon and return in the enclosed envelope. If acting
                                                                            as attorney, executor, administrator, guardian or
                                                                            trustee, please so indicate with your full title
                                                                            when signing. If a corporation, please sign in full
                                                                            corporate name, by duly authorized officer. If shares
                                                                            are held jointly, each stockholder named should sign.


SIGNATURE(S)-------------------------------------------------------------------------------- DATE -----------------------------
Note: Please sign as name appears hereon. Joint owners should each sign. When signing as attorney, executor, administrator, 
      trustee or guardian, please give full title as such.