Exhibit 23.1

CONSENT OF INDEPENDENT REGISTERED PUBLIC ACCOUNTING FIRM

We consent to the incorporation by reference in Registration Statement Nos. 333-49138, 033-22977, 33-22977, and 33-89930 on Form S-8 of our reports dated June 22, 2006, relating to the consolidated financial statements of MAIR Holdings, Inc. and subsidiaries (the “Company”) (which report expresses an unqualified opinion and includes explanatory paragraphs relating to Mesaba Aviation, Inc., a wholly-owned subsidiary of the Company, filing for reorganization under Chapter 11 of the United States Bankruptcy Code on October 13, 2005 and to the restatement of the fiscal 2005 and 2004 consolidated statements of operations), and management’s report on the effectiveness of internal control over financial reporting appearing in this Annual Report on Form 10-K of the Company for the year ended March 31, 2006.

DELOITTE & TOUCHE LLP

Minneapolis, Minnesota

June 22, 2006