Exhibit 99.1

NATIONAL AMERICAN UNIVERSITY HOLDINGS, INC. REPORTS

FISCAL 2012 SECOND QUARTER AND SIX MONTHS RESULTS

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

Financial and Operational Highlights

Rapid City, South Dakota, January 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 second quarter and six months ended November 30, 2011.

The Company, through its wholly owned subsidiary, operates in two business segments: 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 November 30, 2011.

Ronald L. Shape, Ed.D., Chief Executive Officer of the Company, commented, “As a result of continued investment in NAU’s geographic expansion and programmatic development, we achieved double-digit growth in NAU’s enrollment to a record 10,898 students during the fiscal 2012 second quarter. Because of our strategic growth initiatives, SG&A expenses were higher during the period, and we expect these expenses will continue to be high through the third and fourth quarters of this fiscal year. However, as we enter fiscal 2013 we will shift our resources from expanding geographically to growing program offerings and headcount at the existing locations. At the same time, we continue to experience slower regulatory approvals for new locations, which has affected our short-term enrollment growth by approximately 4% to 6% as we cannot begin actively recruiting at these locations until we receive all necessary approvals. We continue to work closely with the appropriate governing bodies to obtain necessary programmatic approvals, and we’re proud to announce last month that our baccalaureate and master’s degree programs in nursing were granted official programmatic accreditation by the Commission on Collegiate Nursing Education (CCNE), a renowned national accreditation agency for nursing. We made improvements at existing locations in Colorado, Kansas, and Texas, and also made progress on development of our new learning

centers in several states during the period. Despite the challenges, we continue to focus on our students, who choose to pursue their studies at NAU because we offer a variety of quality academic programs and the flexibility to also meet their work and family obligations.”

Facility Expansion

The Company’s wholly owned subsidiary currently owns one property and leases 34 physical properties as additional locations or branch campuses in the states of Colorado, Kansas, Minnesota, Missouri, Nebraska, New Mexico, Oklahoma, Oregon, South Dakota and Texas. Of the 34, the following sites are pending regulatory approvals:

NAU’S online academic and degree programs continue to grow. In addition, NAU continues to operate hybrid additional 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

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. For the three months ended November 30, 2011, business expansion and program development expenditures totaled $5.6 million, compared to $3.1 million in the prior-year period. Of the $5.6 million, the Company incurred approximately $3.2 million in marketing, advertising, and admissions expenses. Since 2005, NAU has invested over $44 million to expand and develop physical locations and academic programming, and the Company feels that this continued capital investment has it positioned well for its next phase of vertical growth.

Upon receiving regulatory approval, NAU’s hybrid learning centers have historically become profitable within 12 to 18 months and, on average, each center achieves enrollment of approximately 150 students.

Student Enrollment

Total NAU student enrollment for the fall term of 2011 increased 13.0% to 10,898 students, up from 9,643 in the last fall term. Students enrolled in 95,792 credit hours compared to 87,010 credit hours in the fall term of last year. The current average age of NAU’s students is 34 years, with those seeking undergraduate degrees remaining the highest portion of NAU’s student population (virtually unchanged from the prior year).

The following is a summary of student enrollment at November 30, 2011, and November 30, 2010, by degree type and by instructional delivery method:

2

FY 2012 Second Quarter Financial Results

FY 2012 Six Months Financial Results

3

Balance Sheet Highlights

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 second quarter, the Company had repurchased 127,867 shares of common stock at an average stock price of $7.26.

Conference Call Information

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

The dial-in numbers are:

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

(201) 689-8033 (International)

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=166886.

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

4

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.

Contact Information:

National American University Holdings, Inc.

Dr. Ronald Shape

605-721-5220

rshape@national.edu

Investor Relations Counsel

The Equity Group Inc.

Carolyne Yu

212-836-9610

cyu@equityny.com

Adam Prior

212-836-9606

aprior@equityny.com

5

NATIONAL AMERICAN UNIVERSITY HOLDINGS, INC. AND SUBSIDIARIES

UNAUDITED CONDENSED CONSOLIDATED STATEMENTS OF OPERATIONS

FOR THE THREE MONTHS AND SIX MONTHS ENDED NOVEMBER 30, 2011 AND NOVEMBER 30, 2010

(In thousands except per share data)

6

NATIONAL AMERICAN UNIVERSITY HOLDINGS, INC. AND SUBSIDIARIES

UNAUDITED CONDENSED CONSOLIDATED BALANCE SHEET

AS OF NOVEMBER 30, 2011 AND AUDITED CONDENSED

CONSOLIDATED BALANCE SHEET AS OF MAY 31, 2011

(In thousands except share data)

7

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.

8