Exhibit 5.1

[Opinion of Boutin Jones Inc.]

June 3, 2015

Molina Healthcare, Inc.

200 Oceangate, Suite 100

Long Beach, CA 90802

Ladies and Gentlemen:

This opinion is furnished to you in connection with the prospectus supplement dated June 3, 2015 (the “Prospectus Supplement”), to the prospectus dated May 29, 2015 (the “Base Prospectus”), included in the Registration Statement on Form S-3, Registration No. 333-204558 (the “Registration Statement”), filed by Molina Healthcare, Inc., a Delaware corporation (the “Company”), with the Securities and Exchange Commission (the “Commission”) under the Securities Act of 1933, as amended (the “Securities Act”), with respect to the sale to the Underwriters (as defined below) of an aggregate of 5,000,000 shares (the “Firm Shares”) of the Company’s common stock, $0.001 par value per share (the “Common Stock”), and an additional up to 750,000 shares of Common Stock that may be sold by the Company to the Underwriters (the “Option Shares” and, together with the Firm Shares, the “Shares”) pursuant to an option granted to the underwriters to purchase additional shares.

The Shares are to be sold by the Company pursuant to an underwriting agreement dated June 3, 2015 (the “Underwriting Agreement”) between the Company and the several underwriters named on Schedule A thereto (the “Underwriters”) for whom UBS Securities LLC, Merrill Lynch, Pierce, Fenner & Smith Incorporated and Wells Fargo Securities, LLC are acting as representatives. The Underwriting Agreement will be filed as an exhibit to a Current Report on Form 8-K and incorporated by reference into the Registration Statement.

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 certified or photostatic 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, and subject to the qualifications, assumptions and limitations set forth herein, we are of the opinion that the Shares have been duly authorized and, when the

Molina Healthcare, Inc.

June 3, 2015

Page 2

price at which the Shares will be sold and the number of Shares to be sold has been approved by the Pricing Committee of the Board of Directors of the Company and when the Shares have been duly issued and delivered by the Company against payment therefor in accordance with the terms of the Underwriting Agreement, the Shares will be validly issued, fully paid and non-assessable.

Our opinion is limited to the General Corporation Law of the State of Delaware, and we express no opinion with respect to the laws of any other jurisdiction.

We hereby consent to the filing of this opinion with the Commission as an exhibit to a Current Report on Form 8-K and the Registration Statement in accordance with the requirements of Item 601(b)(5) of Regulation S-K under the Securities Act and to the use of this firm’s name therein and in the Prospectus and the Prospectus Supplement under the caption “Legal Matters.” In giving such consent, we do not hereby admit that we are in the category of persons whose consent is required under Section 7 of the Securities Act or the rules and regulations promulgated thereunder.