Exhibit 5.1

June 14, 2016

Centene Corporation

7700 Forsyth Boulevard

St. Louis, Missouri 63105

Ladies and Gentlemen:

We have acted as counsel to Centene Corporation, a Delaware corporation (the “Company”), in connection with the Company’s filing of a Registration Statement on Form S-3 (No. 333-196037) (the “Registration Statement”) with the Securities and Exchange Commission (the “Commission”) under the Securities Act of 1933, as amended (the “Act”) on May 16, 2014, including the Prospectus dated May 16, 2014, as supplemented by the Prospectus Supplement dated June 9, 2016 (as so supplemented, the “Prospectus”) relating to (i) the sale by the Company and the purchase by the underwriters referred to therein (the “Underwriters”) of $500,000,000 aggregate principal amount of the Company’s 4.75% Senior Notes due 2022 (the “Notes”), issued under an Indenture, dated as of April 29, 2014 (the “Indenture”), between the Company and The Bank of New York Mellon Trust Company, N.A., as trustee (the “Trustee”). All capitalized terms which are defined in the Underwriting Agreement (as defined below) shall have the same meanings when used herein, unless otherwise specified.

In connection herewith, we have examined:

(1) a copy of the Certificate of Incorporation, as amended, of the Company, as certified by the Delaware Secretary of State;

(2) the Bylaws of the Company, as certified by an officer of the Company;

(3) the Registration Statement;

(4) the Indenture;

(5) the form of the Notes;

(6) the Prospectus; and

(7) the Underwriting Agreement, dated June 9, 2016, among the Company, Citigroup Global Markets Inc., Barclays Capital Inc., SunTrust Robinson Humphrey, Inc. and Wells Fargo Securities, LLC, as representatives of the Underwriters, and Evercore Group L.L.C., solely in its capacity as qualified independent underwriter (the “Underwriting Agreement”).

Centene Corporation

June 14, 2016

Page 2

We have also examined originals or copies, certified or otherwise identified to our satisfaction, of such other corporate records, agreements and instruments of the Company, certificates of public officials and officers of the Company, and such other documents, records and instruments, and we have made such legal and factual inquiries, as we have deemed necessary or appropriate as a basis for us to render the opinions hereinafter expressed. In our examination of the foregoing, we have assumed the genuineness of all signatures, the legal competence and capacity of natural persons, the authenticity of documents submitted to us as originals and the conformity with authentic original documents of all documents submitted to us as copies or by facsimile or other means of electronic transmission, or which we obtained from the Commission’s Electronic Data Gathering, Analysis and Retrieval system (“Edgar”) or other sites maintained by a court or governmental authority or regulatory body and the authenticity of the originals of such latter documents. If any document we examined in printed, word processed or similar form has been filed with the Commission on Edgar or such sites maintained by a court or governmental authority or regulatory body, we have assumed that the document so filed is identical to the document we examined except for formatting changes. We have also relied, to the extent that we deemed appropriate, upon the oral advice of the staff of the Commission. When relevant facts were not independently established, we have relied without independent investigation as to matters of fact upon statements of governmental officials and upon representations or warranties made in or pursuant to the Underwriting Agreement and certificates and statements of appropriate representatives of the Company.

In connection herewith, we have assumed that, other than with respect to the Company, all of the documents referred to in this opinion letter have been duly authorized by, have been duly executed and delivered by, and constitute the valid, binding and enforceable obligations of, all of the parties to such documents, all of the signatories to such documents have been duly authorized and all such parties are duly organized and validly existing and have the power and authority (corporate or other) to execute, deliver and perform such documents.

Based upon the foregoing and in reliance thereon, and subject to the assumptions, comments, qualifications, limitations and exceptions set forth herein, we are of the opinion that the Notes have been duly authorized, and when duly executed, authenticated, issued and delivered to the Underwriters, in exchange for payment therefor in accordance with the terms of the Underwriting Agreement, the Notes will constitute valid and binding obligations of the Company, enforceable against the Company in accordance with their terms.

In addition to the assumptions, comments, qualifications, limitations and exceptions set forth above, the opinions set forth herein are further limited by, subject to and based upon the following assumptions, comments, qualifications, limitations and exceptions:

(a) Our opinions herein reflect only the application of (i) applicable New York State law (excluding the securities and blue sky, environmental, employee benefit, insurance, pension, antitrust and tax laws of such State, as to which we express no opinion), (ii) the federal laws of the United States of America (excluding the federal securities, environmental, employee benefit, insurance, pension, antitrust and tax laws, as to which we express no opinion), (iii) to the extent required by the

Centene Corporation

June 14, 2016

Page 3

foregoing opinions, the General Corporation Law of the State of Delaware (including the statutory provisions, all applicable provisions of the Delaware constitution and reported judicial decisions interpreting the foregoing). The opinions set forth herein are made as of the date hereof and are subject to, and may be limited by, future changes in factual matters, and we undertake no duty to advise you of the same. The opinions expressed herein are based upon the law in effect (and published or otherwise generally available) on the date hereof, and we assume no obligation to revise or supplement these opinions should such law be changed by legislative action, judicial decision or otherwise. In rendering our opinions, we have not considered, and hereby disclaim any opinion as to, the application or impact of any laws, cases, decisions, rules or regulations of any other jurisdiction, court or administrative agency.

(b) Our opinions contained herein are limited by (i) applicable bankruptcy, insolvency, reorganization, receivership, moratorium or similar laws affecting or relating to the rights and remedies of creditors generally including, without limitation, laws relating to fraudulent transfers or conveyances, preferences and equitable subordination, (ii) general principles of equity (regardless of whether considered in a proceeding in equity or at law), (iii) an implied covenant of good faith and fair dealing; (iv) requirements that a claim with respect to the Notes denominated other than in United States dollars (or a judgment denominated other than in United States dollars with respect to such a claim) be converted into United States dollars at a rate of exchange prevailing on a date determined pursuant to applicable law, and (v) governmental authority to limit, delay, or prohibit the making of payments outside the United States or in foreign or composite currency.

(c) Our opinions are further subject to the effect of generally applicable rules of law arising from statutes, judicial and administrative decisions, and the rules and regulations of governmental authorities, that: (i) require compliance with or impose standards relating to fiduciary duties or fairness; (ii) limit or affect the enforcement of provisions of a contract that purport to require waiver of the obligations of good faith, fair dealing, diligence and reasonableness; (iii) limit the availability of a remedy under certain circumstances where another remedy has been elected; (iv) limit the enforceability of provisions releasing, exculpating, or exempting a party from, or requiring indemnification of a party for, liability for its own action or inaction, to the extent the action or inaction involves negligence, recklessness, willful misconduct or unlawful conduct; (v) may, where less than all of the contract may be unenforceable, limit the enforceability of the balance of the contract to circumstances in which the unenforceable portion is not an essential part of the agreed exchange; and (vi) govern and afford judicial discretion regarding the determination of damages and entitlement to attorneys’ fees.

(d) We express no opinion as to:

(i) the enforceability of any provision of the Indenture purporting or attempting to (A) confer exclusive jurisdiction and/or venue upon certain courts or otherwise waive the defenses of forum non conveniens or improper venue, (B) confer subject matter jurisdiction on a court not having independent grounds therefor, (C) modify or waive the requirements for effective service of process for any action that may be brought, (D) waive the right of the

Centene Corporation

June 14, 2016

Page 4

Company or any other person to a trial by jury, (E) provide that remedies are cumulative or that decisions by a party are conclusive or (F) modify or waive the rights to notice, legal defenses, statutes of limitations and statutes of repose (including the tolling of the same) or other benefits that cannot be waived under applicable law or (G) govern choice of law or conflict of laws; or (H) provide for or grant a power of attorney; or;

(ii) the enforceability of (A) any rights to indemnification or contribution provided for in the Indenture or the Notes which are violative of public policy underlying any law, rule or regulation (including any Federal or state securities law, rule or regulation) or the legality of such rights, or (B) provisions in the Indenture whose terms are left open for later resolution by the parties.

We hereby consent to the filing of this opinion letter as an exhibit to the Company’s Current Report on Form 8-K and to the use of our name under the caption “Legal Matters” in the Prospectus. In giving such consent, we do not thereby concede that we are within the category of persons whose consent is required under Section 7 of the Act or the rules and regulations of the Commission thereunder.

Very truly yours,

/s/ BRYAN CAVE