Exhibit 5.1

April 2, 2014

Board of Directors

First Interstate BancSystem, Inc.

401 North 31st Street

Billings, MT 59101

Re:              Registration Statement on Form S-4

Ladies and Gentlemen:

We are acting as counsel to First Interstate BancSystem, Inc., a Montana corporation (the “Company”), in connection with its registration statement on Form S-4, as amended (the “Registration Statement”), filed with the Securities and Exchange Commission (the “Commission”) relating to the registration under the Securities Act of 1933, as amended (the “Act”), of up to 1,444,623 shares of the Company’s Class A common stock, no par value per share (the “Shares”), to be issued to the stockholders of Mountain West Financial Corp., a Montana corporation (“MTWF”), in connection with the merger (the “Merger”) of MTWF with and into the Company pursuant to the Agreement and Plan of Merger dated February 10, 2014 by and between the Company and MTWF (collectively with all exhibits and schedules attached thereto, the “Merger Agreement”). This opinion letter is furnished to you at your request to enable you to fulfill the requirements of Item 601(b)(5) of Regulation S-K, 17 C.F.R. § 229.601(b)(5), in connection with the Registration Statement.

For purposes of this opinion letter, we have examined: an executed copy of the Registration Statement; an executed copy of the Merger Agreement; a copy of the Restated Certificate of Incorporation of the Company, as certified by the Secretary of the State of the State of Montana as of a recent date and by the Secretary of the Company on the date hereof as being complete, accurate, and in effect; a copy of the Second Amended and Restated Bylaws of the Company, as certified by the Secretary of the Company on the date hereof as being complete, accurate, and in effect; resolutions of the Board of Directors of the Company (the “Board”), as certified by the Secretary of the Company on the date hereof as being complete, accurate, and in effect, relating to the issuance and sale of the Shares pursuant to the Merger Agreement and related matters; and an officer’s certificate of the Company, dated as of the date hereof, as to certain facts relating to the Company.

In our examination of the aforesaid documents, we have assumed the genuineness of all signatures, the legal capacity of all natural persons, the accuracy and completeness of all documents submitted to us, the authenticity of all original documents, and the conformity to authentic original documents of all documents submitted to us as copies (including electronic or photostatic copies).  In rendering this opinion, we have relied as to certain factual matters on information obtained from public officials, officers or representatives of the Company or other sources believed by us to be responsible and upon the representations and warranties of the Company contained in the Merger Agreement.  This opinion letter is given, and all statements herein are made, in the context of the foregoing.

This opinion letter is based as to matters of law solely on the Montana Business Corporation Act, as amended.  We express no opinion herein as to any other laws, statutes, ordinances, rules or regulations.

Based upon, subject to and limited by the foregoing, we are of the opinion that, as of the date hereof, the Shares have been duly authorized by all necessary corporate action on the part of the Company and, following: (i) effectiveness of the Registration Statement; (ii) the effectiveness of the Merger under applicable law and the issuance of the Shares pursuant to the terms of the Merger Agreement; and (iii) receipt by the Company of the

consideration for the Shares specified in the resolutions of the Board and as set forth in the Merger Agreement, the Shares will be validly issued, fully paid and nonassessable.

This opinion letter has been prepared for your use in connection with the Registration Statement and speaks as of the date hereof.  We assume no obligation to advise you of any changes in the foregoing subsequent to the delivery of this opinion letter.

We hereby consent to the filing of this opinion letter as Exhibit 5.1 to the Registration Statement and to the reference to this firm under the caption “Certain Legal Matters” in the proxy statement/prospectus constituting a part of the Registration Statement.  In giving this consent, we do not thereby admit that we are an “expert” within the meaning of the Act.

Very truly yours,

/s/ HOLLAND & HART LLP