Exhibit 99.1

NATIONAL AMERICAN UNIVERSITY HOLDINGS, INC. REPORTS

FISCAL 2012 THIRD QUARTER AND NINE MONTHS RESULTS

Company to host conference call on April 5, 2012, at 11:00 a.m. ET

Financial and Operational Highlights

Rapid City, South Dakota, April 4, 2012 — National American University Holdings, Inc. (the “Company”) (NASDAQ: NAUH), which through its wholly owned subsidiary operates National American University (“NAU”), a regionally accredited, proprietary, multi-campus institution of higher learning, today reported unaudited financial results for its fiscal year 2012 third quarter and nine months ended February 29, 2012.

Ronald L. Shape, Ed.D., Chief Executive Officer of the Company, commented, “We continue to be very pleased with our top-line growth and profitability, which we feel is a strong accomplishment given our geographic and programmatic expansion in a heightened regulatory environment. NAU has grown from 17 locations to 35 in the past three years (with four pending). NAU increased its enrollment by 10.5% over the same period last year during the fiscal 2012 third quarter, largely as a result of this expansion. Throughout fiscal 2012, we have incurred higher expenses through the addition of staffing, marketing, and facility expense at these new campus locations without offsetting revenue and enrollment. As NAU moves into the fiscal 2013 year, we plan to transition from this geographic expansion strategy to a more vertical approach of growth, developing programs and focusing on enrollment growth at each of our campus locations throughout the U.S., while building on our highly respected academic standards.”

Operating Review

Update on Facility Expansion

NAU currently owns one property and leases 35 physical properties in the states of Colorado, Indiana, Kansas, Minnesota, Missouri, Nebraska, New Mexico, Oklahoma, Oregon, South Dakota and Texas. NAU’S online academic and degree programs continue to grow. In addition, NAU continues to operate additional hybrid locations which utilize small physical facilities in strategic geographic areas, allowing its students to meet face-to-face with staff for assistance on their educational choices and related services while completing the majority of the coursework online.

National American University Holdings, Inc.

April 4, 2012

During the remainder of fiscal year 2012, the Company is committed to moving forward with its campus expansion plans, while closely tracking the expenditures associated with these new educational sites, new program development, and program expansion within the SG&A expense category. The Company expects that its SG&A as a percentage of total revenue will decline as it focuses on increasing enrollment at its existing campus locations over the next fiscal year.

Of the Company’s 35 campuses, the following sites are pending regulatory approvals:

Dr. Shape concluded, “NAU has invested over $50 million in the past seven years to expand and develop physical locations and academic programming. While we continued to experience longer regulatory approval periods for our developing locations and academic programs, we have seen considerable progress over the past three months. Several of our pending campus locations have received staff visits from the respective regulatory body, and recommendations are pending final committee action. We have reviewed the staff’s recommendations and are very satisfied that these approvals are moving forward. We have begun marketing activities for several of these locations and will begin recruitment activities once we receive the final approvals on the other locations. With the approval to enroll students, these locations have historically become profitable within 12 to 18 months, when the center achieves an enrollment of approximately 150-200 students. We expect that these new locations will contribute considerably to our top line, and the investments that we have made over the past 12 months will begin to realize a benefit in fiscal 2013.”

10.5% Enrollment Increase

Total NAU student enrollment for the winter term of 2012 increased 10.5% to 10,968 students, up from 9,930 in the last winter term. Students enrolled in 96,745 credit hours compared to 88,725 credit hours in the winter term of last year. The current average age of NAU’s students is in the mid-30s, with those seeking undergraduate degrees remaining the highest portion of NAU’s student population.

The following is a summary of student enrollment at February 29, 2012, and February 28, 2011, by degree type and by instructional delivery method:

Page 2

National American University Holdings, Inc.

April 4, 2012

Formation of Community College Advisory Board

In November 2011, NAU developed a Community College Advisory Board consisting of nationally renowned members to strengthen its relationships with community colleges. The Community College Advisory Board serves as an advisory and decision-making group under the direction of the Chair, Dr. John E. Roueche, on matters related to the university’s academic programs, services and initiatives associated with community colleges. Dr. Roueche holds the Sid Richardson Regents Chair at the University of Texas at Austin, where he directs the Community College Leadership Program. Dr. Roueche and the other members of the Advisory Board are considered recognized authorities in community college education.

With direction from the Advisory Board, NAU continues to build relationships that it believes will assist in building alliances to meet the needs of community college students, staff, and faculty. In March 2012, NAU met with several Community College leaders from the Kansas and Missouri areas to discuss specific needs and next steps for building these relationships.

Financial Review

The Company, through its wholly owned subsidiary, operates in two business segments: the academic segment, which consists of NAU’s undergraduate and graduate education programs and contributes the primary portion of the Company’s revenue; and ownership in multiple apartments and condominium complexes from which it derives sales and rental income. The real estate operations generated approximately 1% of the Company’s revenues for the quarter ended February 29, 2012.

Fiscal 2012 Third Quarter

For the three months ended February 29, 2012, this expense was $7.0 million, or 23.4% of the academic segment’s total revenue, compared to $5.6 million, or 20.4%, for the three months ended February 28, 2011. This increase was primarily a result of expenses incurred from increased instructional compensation and hiring the additional faculty and staff necessary to support the larger student population.

FY 2012 Nine Months Financial Results

Page 3

National American University Holdings, Inc.

April 4, 2012

Balance Sheet Highlights

(* Decrease largely due to shareholder repurchases during the period)

Stock Repurchase Plan Update

On November 4, 2011, the Company announced that its Board of Directors had authorized the establishment of a stock repurchase program for the Company to purchase up to $10 million of common stock in both open market and privately negotiated transactions. By the end of the third quarter, the Company had repurchased 835,058 shares of common stock at an average stock price of $7.07.

Quarterly Dividend

The Company’s Board of Directors declared a cash dividend in the amount of $0.0325 per share on all shares of the Company’s common stock outstanding and of record as of the close of business on March 30, 2012, to be paid on or about April 6, 2012.

Conference Call Information

The Company will discuss these results in a conference call (with accompanying presentation) on April 5, 2012, at 11:00 a.m. ET.

The dial-in numbers are:

(877) 407-8033 (U.S.)

(201) 689-8033 (International)

Page 4

National American University Holdings, Inc.

April 4, 2012

Accompanying Slide Presentation and Webcast

The Company will also have an accompanying slide presentation available in PDF format at the “Investor Relations” section of the NAU website at http://www.national.edu/InvestorRelations. The presentation will be made available 30 minutes prior to the conference call. In addition, the call will be simultaneously webcast over the Internet via the “Investor Relations” section of the NAU website or by clicking on the conference call link: http://www.investorcalendar.com/IC/CEPage.asp?ID=167861.

About National American University Holdings, Inc.

National American University Holdings, Inc., through its wholly owned subsidiary, operates National American University (“NAU”), a regionally accredited, proprietary, multi-campus institution of higher learning offering associate, bachelor’s, and master’s degree programs in health care and business-related disciplines. Accredited by The Higher Learning Commission and a member of the North Central Association of Colleges and Schools, NAU has been providing technical and professional career education since 1941. NAU opened its first campus in Rapid City, South Dakota, and has since grown to multiple locations throughout the central United States. In 1998, NAU began offering online courses. Today, NAU offers degree programs in traditional, online, and hybrid formats, which provides students increased flexibility to take courses at times and places convenient to their busy lifestyles.

Forward Looking Statements

This press release may contain forward-looking statements within the meaning of the Private Securities Litigation Reform Act of 1995 regarding the Company’s business. Statements made in this release, other than those concerning historical financial information, may be considered forward-looking statements, which speak only as of the date of this release and are based on current beliefs and expectations and involve a number of assumptions. These forward-looking statements include outlooks or expectations for earnings, revenues, expenses or other future financial or business performance, strategies or expectations, or the impact of legal or regulatory matters on business, results of operations or financial condition. Specifically, forward-looking statements may include statements relating to the future financial performance of the Company; the ability to continue to receive Title IV funds; the growth of the market for the Company’s services; expansion plans and opportunities; consolidation in the market for the Company’s services generally; and other statements preceded by, followed by or that include the words “estimate,” “plan,” “project,” “forecast,” “intend,” “expect,” “anticipate,” “believe,” “seek,” “target” or similar expressions. These forward-looking statements involve a number of known and unknown risks and uncertainties or other assumptions that may cause actual results or performance to be materially different from those expressed or implied by those forward-looking statements. Other factors that could cause the Company’s results to differ materially from those contained in its forward-looking statements are included under, among others, the heading “Risk Factors” in the Company’s Annual Report on Form 10-K, which was filed on August 5, 2011, and in its other filings with the Securities and Exchange Commission. The Company assumes no obligation to update the information contained in this release.

Page 5

National American University Holdings, Inc.

April 4, 2012

NATIONAL AMERICAN UNIVERSITY HOLDINGS, INC. AND SUBSIDIARIES

UNAUDITED CONDENSED CONSOLIDATED STATEMENTS OF OPERATIONS

FOR THE THREE MONTHS AND NINE MONTHS ENDED FEBRUARY 29, 2012 AND FEBRUARY 28, 2011

(In thousands except per share data)

Page 6

National American University Holdings, Inc.

April 4, 2012

NATIONAL AMERICAN UNIVERSITY HOLDINGS, INC. AND SUBSIDIARIES

UNAUDITED CONDENSED CONSOLIDATED BALANCE SHEET

AS OF FEBRUARY 29, 2012 AND AUDITED CONDENSED

CONSOLIDATED BALANCE SHEET AS OF MAY 31, 2011

(In thousands except share data)

Page 7

National American University Holdings, Inc.

April 4, 2012

The following table provides a reconciliation of net income attributable to the Company to EBITDA:

Consists of income attributable to the Company, less income from non-controlling interest, plus loss from non-controlling interest, minus interest income, plus interest expense, plus income taxes, plus depreciation and amortization. The Company uses EBITDA as a measure of operating performance. However, EBITDA is not a recognized measurement under U.S. generally accepted accounting principles, or GAAP, and when analyzing its operating performance, investors should use EBITDA in addition to, and not as an alternative for, income as determined in accordance with GAAP. Because not all companies use identical calculations, its presentation of EBITDA may not be comparable to similarly titled measures of other companies and is therefore limited as a comparative measure. Furthermore, as an analytical tool, EBITDA has additional limitations, including that (a) it is not intended to be a measure of free cash flow, as it does not consider certain cash requirements such as tax payments; (b) it does not reflect changes in, or cash requirements for, its working capital needs; and (c) although depreciation and amortization are non-cash charges, the assets being depreciated and amortized often will have to be replaced in the future, and EBITDA does not reflect any cash requirements for such replacements, or future requirements for capital expenditures or contractual commitments. To compensate for these limitations, the Company evaluates its profitability by considering the economic effect of the excluded expense items independently as well as in connection with its analysis of cash flows from operations and through the use of other financial measures.

The Company believes EBITDA is useful to an investor in evaluating its operating performance because it is widely used to measure a company’s operating performance without regard to certain non-cash expenses (such as depreciation and amortization) and expenses that are not reflective of its core operating results over time. The Company believes EBITDA presents a meaningful measure of corporate performance exclusive of its capital structure, the method by which assets were acquired and non-cash charges, and provides us with additional useful information to measure its performance on a consistent basis, particularly with respect to changes in performance from period to period.

Page 8