Exhibit 5.1

Opinion of Haynes and Boone, LLP

June 13, 2016

Callon Petroleum Company

200 North Canal Street

Natchez, Mississippi 39120

Re: Registration Statement on Form S-8 of 2,000,000 Shares of Common Stock of Callon Petroleum Company

Ladies and Gentlemen:

We have acted as counsel to Callon Petroleum Company, a Delaware corporation (the “Company”), in connection with the filing with the Securities and Exchange Commission (the “Commission”) under the Securities Act of 1933, as amended (the “Act”) of a registration statement on Form S-8 (the “Registration Statement”) by the Company relating to the registration of 2,000,000 shares (the “Shares”) of the Company’s common stock, $0.01 par value per share (the “Common Stock”), issuable pursuant to the Company’s 2011 Omnibus Incentive Plan, as amended (the “Plan”).

This opinion is being furnished in accordance with the requirements of Item 601(b)(5) of Regulation S-K under the Act.

For purposes of the opinions we express below, we have examined originals, or copies certified or otherwise identified, of (i) the Certificate of Incorporation, as amended (the “Certificate of Incorporation”) and Bylaws of the Company (the “Bylaws”), each as amended as of the date hereof, (ii) certain resolutions of the Board of Directors of the Company related to the filing of the Registration Statement, the authorization and issuance of the Shares and related matters, (iii) the Registration Statement and all exhibits thereto, (iv) the Plan, (v) the specimen Common Stock certificate, (vi) a certificate executed by an officer of the Company, dated as of the date hereof, and (vii) such other records, documents and instruments as we deemed relevant and necessary for purposes of the opinion stated herein.

As to questions of fact material to the opinions expressed below, we have, without independent verification of their accuracy, relied to the extent we deem reasonably appropriate upon the representations and warranties of the Company contained in such documents, records, certificates, instruments or representations furnished or made available to us by the Company.

In making the foregoing examination, we have assumed (i) the genuineness of all signatures, (ii) the authenticity of all documents submitted to us as originals, (iii) the conformity to original documents of all documents submitted to us as certified or photostatic copies, (iv) that all agreements or instruments we have examined are the valid, binding and enforceable obligations of the parties thereto, and (v) that all factual information on which we have relied was accurate and complete.

We have not considered, and express no opinion herein as to, the laws of any state or jurisdiction other than the Delaware General Corporation Law, as currently in effect (the “DGCL”).

We have also assumed that, at the time of the issuance of the Shares, (i) the Registration Statement and any amendments thereto (including post-effective amendments) will have become effective and will remain effective, (ii) no stop order of the Commission preventing or suspending the use of the prospectus described in the Registration Statement will have been issued, (iii) the prospectus described in the Registration Statement and any required prospectus supplement will have been delivered to the recipient of the Shares as required in accordance with applicable law, (iv) the resolutions of the Board of Directors of the Company referred to above will not have been modified or rescinded, (v) the Company will receive consideration for the issuance of the Shares required by the Plan and that is at least equal to the par value of the Common Stock, (vi) all requirements of the DGCL, the Certificate of Incorporation and the Bylaws will be complied with when the Shares are issued, (vii) sufficient shares of Common Stock will be authorized for issuance under the Certificate of Incorporation of the Company that have not otherwise been issued or reserved for issuance and (viii) neither the issuance nor sale of the Shares will result in a violation of any agreement or instrument then binding upon the Company or any order of any court or governmental body having jurisdiction over the Company.

Based on the foregoing, and subject to the qualifications, assumptions and limitations stated herein, we are of the opinion that upon the issuance of the Shares in accordance with the terms of the Plan and the instruments executed pursuant to such Plan, the Shares will be validly issued, fully paid and non-assessable.

We hereby consent to the filing of this opinion as Exhibit 5.1 to the Registration Statement and to the reference to our firm under the heading “Legal Matters” in the prospectus constituting a part of the Registration Statement. In giving this consent, we are not admitting 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/ Haynes and Boone, LLP