Exhibit 5

November 2, 2012

Nathan’s Famous, Inc.

One Jericho Plaza

Jericho, New York 11753

Re: Registration Statement on Form S-8

Ladies and Gentlemen:

We have acted as counsel to Nathan’s Famous, Inc., a Delaware corporation (the “Company”), in connection with the filing of its registration statement on Form S-8 (the “Registration Statement”) relating to the registration of 250,000 shares (the “Shares”) of the Company’s common stock, par value $0.01 per share (the “Common Stock”) issuable pursuant to the terms and in the manner set forth in the Company’s 2010 Stock Incentive Plan, as amended (the “Plan”).

This opinion letter is being delivered at the request of the Company and in accordance with the requirements of Item 601(b)(5) of Regulation S-K promulgated by the Securities and Exchange Commission.

We advise you that we have examined originals or copies certified or otherwise identified to our satisfaction of the Registration Statement, the Plan, the Certificate of Incorporation and By-laws, each as amended, and corporate proceedings of the Company, and such other documents, instruments and certificates of officers and representatives of the Company and of public officials, and we have made such examination of law, as we have deemed appropriate as the basis for the opinion hereinafter expressed. In making such examination, we have assumed the genuineness of all signatures, the legal capacity of natural persons, the authenticity and completeness of documents submitted to us as originals, the conformity to original documents of documents submitted to us as certified or photostatic copies, and the authenticity and completeness of the originals of such latter documents.

Based upon the foregoing, we are of the opinion that the Shares to be issued under the Plan, when issued pursuant to the terms and in the manner set forth in the Plan, will be duly and validly issued, fully paid and non-assessable.

We are members of the Bar of the State of New York. We express no opinion as to the effects of any laws, statutes, regulations or ordinances other than the laws of the State of New York and of the United States of America.

We hereby consent to the filing of this opinion as an exhibit to the Registration Statement. In giving such consent, we do not thereby concede that our firm is within the category of persons whose consent is required under Section 7 of the Securities Act or the rules and regulations of the Commission.

Very truly yours,

/s/ OLSHAN FROME WOLOSKY LLP