Exhibit 5.1

[Opinion of Boutin Jones Inc.]

May 29, 2015

Molina Healthcare, Inc.

200 Oceangate, Suite 100

Long Beach, CA 90802

Re: Molina Healthcare, Inc.

Registration Statement on Form S-3

Ladies and Gentlemen:

At your request, we have examined the Registration Statement on Form S-3 (the “Registration Statement”) scheduled to be filed today by Molina Healthcare, Inc., a Delaware corporation (the “Company”), with the Securities and Exchange Commission pursuant to the Securities Act of 1933, as amended (the “Securities Act”). The Registration Statement relates to the proposed issuance and sale from time to time (1) by the Company of (a) shares of the Company’s common stock, par value $0.001 per share (the “Common Stock”); (b) shares of preferred stock, par value $0.001 per share (the “Preferred Stock”); (c) the Company’s senior debt securities and subordinated debt securities (collectively, the “Debt Securities”), which may be issued pursuant to a senior debt indenture (the “Senior Debt Indenture”) between the Company and a trustee to be named therein (the “Senior Debt Trustee”) and a subordinated debt indenture (the “Subordinated Indenture” and, together with the Senior Indenture, the “Indentures”) between the Company and a trustee to be named therein (the “Subordinated Debt Trustee” and, together with the Senior Debt Trustee, the “Trustees”); (d) warrants of the Company (the “Warrants”) to purchase Common Stock, Preferred Stock, Debt Securities, or any combination of the foregoing, which may be issued pursuant to a warrant agreement (the “Warrant Agreement”) between the Company and a warrant agent to be named therein (the “Warrant Agent”); (e) securities purchase contracts obligating the holders thereof to buy Common Stock, Preferred Stock or Debt Securities from the Company at future dates (“Securities Purchase Contracts”); (f) depositary shares of the Company (the “Depositary Shares”), each representing a fractional interest in a share of Preferred Stock and evidenced by a deposit receipt (the “Deposit Receipts”), which may be issued pursuant to a deposit agreement among the Company, a depositary to be named therein (the “Depositary”) and the holders from time to time of the Deposit Receipts issued thereunder (the “Deposit Agreement”); and (g) units (the “Units”) which may be issued under one or more unit agreements (each such unit agreement, a “Unit Agreement”) entered into between the Company and a bank or trust company, as unit agent (the “Unit Agent”); and (2) by certain selling stockholders to be named in a Prospectus Supplement (as defined below) of Common Stock (the “Selling Stockholder Securities”).

The offering of the Common Stock, the Preferred Stock, the Debt Securities, the Warrants, the Securities Purchase Contracts, the Depositary Shares and the Units (each, a “Security” and, collectively, the “Securities”), and the Selling Stockholder Securities, will be as set forth in the prospectus contained in the Registration Statement, as supplemented by one or more supplements to the Prospectus (each, a “Prospectus Supplement”).

In connection with this opinion, we have examined such documents and such matters of fact and law that we have deemed necessary for the purpose of rendering the opinion set forth herein. In such examination, we have assumed without verification (a) the authenticity of original documents and the genuineness of all signatures, (b) the conformity to originals of all documents submitted to us as copies, and (c) the truth, accuracy and completeness of the information, representations and warranties contained in the records, documents, instruments and certificates examined by us.

Based upon the foregoing, we are of the opinion that:

1. When the necessary corporate action on the part of the Company has been taken to authorize the issuance and sale of such shares of Common Stock proposed to be sold by the Company, and when such shares of

Molina Healthcare, Inc.

May 29, 2015

Page 2 of 3

Common Stock are issued and delivered in accordance with the applicable underwriting or other agreement against payment therefor (in excess of par value thereof) or upon conversion or exercise of any Security offered under the Registration Statement (the “Offered Security”), in accordance with terms of such Offered Security or the instrument governing such Offered Security providing for such conversion or exercise as approved by the Board of Directors of the Company, for the consideration approved by the Board of Directors of the Company (which consideration is not less than the par value of the Common Stock), such shares of Common Stock will be validly issued, fully-paid and non-assessable.

2. Upon designation of the relative rights, preferences and limitations of any series of Preferred Stock by the Board of Directors of the Company in accordance with the Company’s then operative amended and restated certificate of incorporation and the proper filing with the Secretary of State of the State of Delaware of a Certificate of Designations relating to such series of Preferred Stock, all necessary corporate action on the part of the Company will have been taken to authorize the issuance and sale of such series of Preferred Stock proposed to be sold by the Company, and when such shares of Preferred Stock are issued and delivered in accordance with any applicable securities purchase agreement or the applicable underwriting or other agreement against payment therefor (in excess of par value thereof), such shares of Preferred Stock will be validly issued, fully paid and non-assessable.

3. When the Indenture and any supplemental indenture to be entered into in connection with the issuance of any series of Debt Securities have been duly authorized, executed and delivered by the Trustee and the Company, the specific terms of a particular series of Debt Securities have been duly authorized and established in accordance with the Indenture, and such series of Debt Securities have been duly authorized, executed, authenticated, issued and delivered in accordance with the Indenture, any applicable Warrant or securities purchase agreement or the applicable underwriting or other agreement against payment therefor, such Debt Securities will constitute valid and binding obligations of the Company, enforceable against the Company in accordance with their terms.

4. When the Warrant Agreement to be entered into in connection with the issuance of any Warrants has been duly authorized, executed and delivered by the Warrant Agent and the Company, the specific terms of the Warrants have been duly authorized and established in accordance with the Warrant Agreement, and such Warrants have been duly authorized, executed, issued and delivered in accordance with the Warrant Agreement and the applicable underwriting or other agreement against payment therefor, such Warrants will constitute valid and binding obligations of the Company, enforceable against the Company in accordance with their terms.

5. When specific terms of the Securities Purchase Contracts have been approved by all necessary corporate action on the part of the Company, the Securities Purchase Contracts have been duly authorized, executed and delivered by the purchasers thereof and the Company, and the Securities Purchase Contracts have been issued and sold in accordance with the applicable purchase, underwriting or other agreement against payment therefor, such Securities Purchase Contracts will constitute valid and binding obligations of the Company, enforceable against the Company in accordance with their terms.

6. When the Deposit Agreement to be entered into in connection with the issuance of any Depositary Shares has been duly authorized, executed and delivered by the Depositary and the Company, the specific terms of the Depositary Shares have been duly authorized and established in accordance with the Deposit Agreement, the underlying series of Preferred Stock has been validly issued as described in paragraph 2 above, the Depositary has duly issued the Deposit Receipts evidencing the Depositary Shares against deposit of the Preferred Stock in respect thereof in accordance with the Deposit Agreement, and the Deposit Receipts have been duly executed, issued and delivered by one of the Depositary’s authorized officers in accordance with the Deposit Agreement and the applicable underwriting or other agreement against payment therefor, such Deposit Receipts will constitute valid and binding obligations of the Company, enforceable against the Company in accordance with their terms.

Molina Healthcare, Inc.

May 29, 2015

Page 3 of 3

7. When the Unit Agreement to be entered into in connection with the issuance of any Units has been duly authorized, executed and delivered by the Unit Agent and the Company, the specific terms of the Units have been duly authorized and established in accordance with the Unit Agreement, and such Units have been duly authorized, executed, issued and delivered in accordance with the Unit Agreement and the applicable underwriting or other agreement against payment therefor, such Units will constitute valid and binding obligations of the Company, enforceable against the Company in accordance with their terms.

The opinions set forth in paragraphs 3, 4, 5, 6 and 7 above are subject in each case to the effect of any bankruptcy, insolvency, reorganization, moratorium, arrangement or similar laws affecting the enforcement of creditors’ rights generally (including, without limitation, the effect of statutory or other laws regarding fraudulent transfers or conveyances or preferential transfers or conveyances) and general principles of reasonableness and equity, regardless of whether enforceability is considered in a proceeding in equity or at law.

In connection with the opinions expressed above, we have assumed that, at or prior to the time of the delivery of any Security, (i) the Board of Directors shall have duly established the terms of such security and duly authorized the issuance and sale of such security and such authorization shall not have been modified or rescinded; (ii) the Registration Statement and any amendments thereto (including post-effective amendments) shall have been declared effective and shall comply with all applicable laws at the time such Security is offered or issued, and such effectiveness shall not have been terminated or rescinded; (iii) a Prospectus Supplement will have been prepared and filed with the Securities and Exchange Commission describing the Securities offered thereby and will comply with all applicable laws; (iv) all Securities will be issued and sold in compliance with applicable federal and state securities laws (including, without limitation, with respect to any Debt Securities, the Trust Indenture Act of 1939, as amended) and in the manner stated in the Registration Statement and the appropriate Prospectus Supplement; (v) a definitive purchase, underwriting or similar agreement with respect to any Securities offered will have been duly authorized and validly executed and delivered by the Company and the other parties thereto; (vi) any Securities issuable upon conversion, exchange or exercise of any Security being offered or issued will be duly authorized, created and, if appropriate, reserved for issuance upon such conversion, exchange or exercise; and (vii) there shall not have occurred any change in law affecting the validity or enforceability of such Security. We have also assumed that none of the terms of any Security to be established subsequent to the date hereof, nor the issuance and delivery of such Security, nor the compliance by the Company with the terms of such Security will violate any applicable law or public policy or will result in a violation of any provision of any instrument or agreement then binding upon the Company, or any restriction imposed by any court or governmental body having jurisdiction over the Company.

The opinions expressed herein are limited to the federal laws of the United States of America, the General Corporation Law of the State of Delaware and, as to the Debt Securities constituting valid and legally binding obligations of the Company, the laws of the State of New York.

We hereby consent to the filing of this opinion as an exhibit to the Registration Statement and to the reference to our firm under the caption “Legal Matters” in the Prospectus which forms part of the Registration Statement. In giving this consent, we do not admit we are included in the category of persons whose consent is required under Section 7 of the Securities Act or the rules and regulations promulgated thereunder.

Very truly yours,

/s/ BOUTIN JONES INC.