Exhibit 23.1

Consent of Independent Registered Public Accounting Firm

We consent to the incorporation by reference in the Registration Statements (Form S-8 No. 333-106495 and Form S-8 No. 333-69490) pertaining to the First Interstate BancSystem, Inc. 2001 Stock Option Plan, as amended; and Registration Statement (Form S-8 No. 333-133837) pertaining to the First Interstate BancSystem, Inc. 2006 Equity Compensation Plan, as amended, of our reports dated February 28, 2013, relating to our audits of the consolidated financial statements and internal control over financial reporting which appear in the Annual Report on Form 10-K of First Interstate BancSystem, Inc. for the year ended December 31, 2012.

/s/ MCGLADREY LLP

Des Moines, Iowa

February 28, 2013