Exhibit 5.1

August 20, 2013

Contango Oil & Gas Company

3700 Buffalo Speedway

Suite 960

Houston, Texas 77098

RE: Contango Oil & Gas Company, Registration Statement on Form S-4 (Registration No. 333-189302)

Ladies and Gentlemen:

We have acted as counsel to Contango Oil & Gas Company , a Delaware corporation (the “Company”), in connection with the filing of the referenced Registration Statement (the “Registration Statement”) under the Securities Act of 1933, as amended (the “Act”), with the Securities and Exchange Commission (the “SEC”). The Registration Statement relates to the proposed offering of up to 4,005,056 shares of common stock, par value $0.04 per share, of the Company (the “Shares”) in connection with the merger contemplated by the Agreement and Plan of Merger, dated as of April 29, 2013, (the “Merger Agreement”), by and among the Company, Crimson Exploration, Inc. and Contango Acquisition, Inc.

In connection with this opinion letter, we have examined the Registration Statement and originals, or copies certified or otherwise identified to our satisfaction, of the Certificate of Incorporation and Bylaws of the Company and such other documents, records and other instruments as we have deemed appropriate for purposes of the opinion set forth herein.

We have assumed the genuineness of all signatures, the legal capacity of all natural persons, the authenticity of the documents submitted to us as originals, the conformity with the originals of all documents submitted to us as certified, facsimile or photostatic copies and the authenticity of the originals of all documents submitted to us as copies.

Based upon the foregoing, we are of the opinion that the Shares have been duly authorized by the Company and, when issued by the Company in accordance with the terms of the Merger Agreement, the Shares will be validly issued, fully paid and non-assessable.

The opinions expressed herein are limited to the Delaware General Corporation Law.

We hereby consent to the use of this opinion as Exhibit 5.1 to the Registration Statement and to the reference to us under the caption “Legal Matters” in the Joint Proxy Statement/Prospectus included in the Registration Statement. In giving such consent, we do not hereby admit that we are acting within the category of persons whose consent is required under Section 7 of the Act or the rules or regulations of the SEC thereunder.

Very truly yours,

/s/ Morgan, Lewis & Bockius LLP