National American University (NAUH) S-1/A IPO registration (amended)

Exhibit 5.1

National American University Holdings, Inc.

5301 S. Hwy 16, Suite 200

Rapid City, South Dakota 57701

Re: Registration Statement on Form S-1 (333-165641)

Ladies and Gentlemen:

You have requested our opinion with respect to certain matters in connection with the filing by National American University Holdings, Inc., a Delaware corporation (the “Company”), of a Registration Statement on Form S-1 (File No. 333-165641) initially filed on March 23, 2010 (as amended and supplemented from time to time, the “Registration Statement”) with the Securities and Exchange Commission, including a related prospectus filed with the Registration Statement (the “Prospectus”) covering the offering for sale of an aggregate of up to 7,000,000 (or 8,050,000 if the underwriters exercise their over-allotment option) shares of the Company’s common stock, $0.0001 par value, 3,500,000 (or 4,550,000 if the underwriters exercise their over-allotment option) of which will be sold by the Company (the “Company Shares”) and 3,500,000 of which will be sold by the selling stockholders (the “Selling Stockholder Shares,” and together with the Company Shares, the “Shares”) named therein. None of the Shares are currently outstanding.

This opinion is being furnished in accordance with the requirements of Item 601(b)(5)(i) of Regulation S-K.

In connection with this opinion, we have reviewed and relied upon the Registration Statement and related Prospectus, the Company’s charter documents, as amended and restated to date, resolutions adopted by the Board of Directors of the Company, minutes of meetings of the Board of Directors of the Company and such other documents, records, certificates, memoranda and other instruments as we deemed necessary as a basis for this opinion. With respect to the foregoing documents, we have assumed the genuineness of all signatures, the authenticity of all documents submitted to us as original and the conformity to originals of all documents submitted to us as certified or reproduced copies. We have also obtained from officers of the Company certificates as to certain factual matters and, insofar as this opinion is based on matters of fact, we have relied on such certificates without independent investigation.

Based upon and subject to the foregoing qualifications, assumptions and limitations and the further limitations set forth below, we are of the opinion that:

(a) The Company Shares have been duly authorized, and, when the Registration Statement becomes effective under the Securities Act of 1933, as amended (the “Act”), when the Board of Directors and the Pricing Committee of the Company have taken all necessary action to approve the issuance and sale of the Company Shares and, if issued as certificated shares, when appropriate certificates representing the Company Shares are duly executed by the Company,

countersigned and registered by the Company’s transfer agent/registrar and delivered to the purchasers of the Company Shares, or if issued as uncertificated shares upon authorization thereof pursuant to the foregoing action of the Board of Directors or Pricing Committee, against payment of the agreed consideration, the Company Shares will be validly issued, fully paid and nonassessable.

(b) The Selling Stockholder Shares have been duly authorized, and will, when such Selling Stockholder Shares are issued upon conversion of the Company’s Class A common stock and, if issued as certificated shares, certificates representing such Selling Stockholder Shares have been duly executed by the Company, countersigned and registered by the Company’s transfer agent/registrar and delivered on behalf of the Company, or if issued as uncertificated shares upon authorization thereof by action of the Board of Directors or the Pricing Committee, against surrender of the certificates representing the Company’s Class A common stock, be validly issued, fully paid and nonassessable.

The opinions expressed herein are limited to the Delaware Corporation, the General Corporation Law of the State of Delaware and reported judicial decisions interpreting those laws, each as currently in effect.

We consent to the filing of this opinion letter as Exhibit 5.1 to the Registration Statement and to the reference to this firm under the caption “Legal Matters” in the Registration Statement. In giving this consent, we do not admit that we are within the category of persons whose consent is required under Section 7 of the Act, the rules and regulations of the Securities and Exchange Commission promulgated thereunder or Item 509 of Regulation S-K.

This opinion letter is rendered to you solely for use in connection with the sale of the Shares in accordance with the Registration Statement as of the date first written above and is not to be relied on for any other purpose. We disclaim any obligation to advise you of facts, circumstances, events or developments that hereafter may be brought to our attention and that may alter, affect or modify the opinion expressed herein. Our opinion is expressly limited to the matters set forth above and we render no opinion, whether by implication or otherwise, as to any other matters relating to the Company or the Shares.

Very truly yours,

Gray, Plant, Mooty, Mooty & Bennett, P.A.