Exhibit 5.1

Opinion of Holland & Hart LLP

May 5, 2006

First Interstate BancSystem, Inc.
401 North 31st Street
Billings, MT 59116

Ladies and Gentlemen:

     We have acted as counsel to First Interstate BancSystem, Inc., a Montana corporation (the “Company”), in connection with the registration under the Securities Act of 1933 (the “Securities Act”) of 750,000 shares of the Company’s common stock, no par value (the “Shares”), to be offered upon the terms and subject to the conditions set forth in the First Interstate BancSystem, Inc. 2006 Equity Compensation Plan (the “Plan”).

     In connection therewith, we have examined originals or copies, certified or otherwise identified to our satisfaction, of the Articles of Incorporation of the Company, the Bylaws of the Company, the Plan, records of relevant corporate proceedings with respect to the offering of the Shares and such other documents, instruments and corporate proceedings with respect to the offering of the Shares and such other documents, instruments and corporate records as we have deemed necessary or appropriate for the expression of the opinion contained herein. We have also reviewed the Company’s Registration Statement on Form S-8 (the “Registration Statement”) to be filed under the Securities Act with the Securities and Exchange Commission on May 5, 2006 with respect to the Shares.

     We have assumed the authenticity and completeness of all records, certificates and other instruments submitted to us as originals, the conformity to original documents of all records, certificates and other instruments submitted to us as copies, the authenticity and completeness of the originals of those records, certificates and other instruments submitted to us as copies and the correctness of all statements of fact contained in all records, certificates and other instruments that we have examined.

     Based on the foregoing, we are of the opinion that the Shares have been duly authorized and, when issued in accordance with the terms of the Plan, will be validly issued, fully paid and non-assessable.

     The opinion expressed herein is based solely upon and is limited to the general corporation laws of the State of Montana and the federal laws of the United States of America, to the extent applicable.

     We hereby consent to the filing of this opinion as an exhibit to the Registration Statement.

Very truly yours,
 

/s/ Holland & Hart llp