Exhibit 23.1

Consent of McGladrey & Pullen LLP, Independent Registered Public Accounting Firm

We hereby consent to the incorporation by reference in this Registration Statement on Form S-8 of our report dated February 1, 2006 relating to the consolidated financial statement of First Interstate BancSystem, Inc. included in First Interstate BancSystem, Inc.’s Annual Report on Form 10-K for the year ended December 31, 2005 filed with the Securities and Exchange Commission.

/s/ MCGLADREY & PULLEN LLP

Des Moines, Iowa
May 4, 2006