Exhibit 5.1

July 15, 2008

Stone Energy Corporation
625 East Kaliste Saloom Rd.
Lafayette, LA 70508

Ladies and Gentlemen:

     We have acted as counsel to Stone Energy Corporation, a Delaware corporation (“Stone”), in connection with the issuance by Stone of shares of common stock, par value $0.01 per share, of Stone (the “Common Stock”) pursuant to an Agreement and Plan of Merger, dated as of April 30, 2008 (the “Merger Agreement”), by and among Stone, Stone Energy Offshore, L.L.C., a Delaware limited liability company, and Bois d’Arc Energy, Inc., a Nevada corporation.

     This opinion is being furnished in accordance with the requirements of Item 601(b)(5) of Regulation S-K under the Securities Act of 1933, as amended (the “Securities Act”).

     In connection with this opinion, we have examined originals or copies, certified or otherwise identified to our satisfaction of (i) the Company’s Registration Statement (as amended, the “Registration Statement”) on Form S-4 (File No. 333-151509) as filed with the Securities and Exchange Commission (the “Commission”) on June 6, 2008, (ii) Amendment No. 1 to the Registration Statement to be filed with the Commission on July 15, 2008, (iii) the Certificate of Incorporation of Stone, as amended, (iv) the Bylaws of Stone, as amended and restated, and (v) certain resolutions adopted by the Board of Directors of Stone with respect to the Merger Agreement and the issuance of the shares of Common Stock contemplated thereby. We have also examined originals or copies, certified or otherwise identified to our satisfaction, of such records of Stone and such agreements, certificates of public officials, certificates of officers or other representatives of Stone and others, and such other documents, certificates and records, as we have deemed necessary or appropriate as a basis for the opinion set forth herein.

     In our examination, we have assumed the legal capacity of all natural persons, the genuineness of all signatures, the authenticity of all documents submitted to us as originals, the conformity to original documents of all documents submitted to us as certified, conformed or photostatic copies and the authenticity of the originals of such latter documents. In making our examination of executed documents, we have assumed that the parties thereto, other than Stone, its directors and officers, had the power, corporate or other, and execution and delivery by such parties of such documents and the validity and binding effect thereof on such parties. As to any facts material to the opinions expressed herein that we have not independently established or verified, we have relied upon statements and representations of officers and other representatives of Stone and others and the disclosures made by Stone in the Registration Statement.

Page 2

     Based upon and subject to the foregoing, and assuming the approval by the stockholders of Stone of the issuance of shares of Common Stock pursuant to the Merger Agreement, we are of the opinion that such shares of Common Stock, when issued in accordance with the terms of the Merger Agreement, will be duly authorized, validly issued, fully paid, and nonassessable.

     The foregoing opinion is limited in all respects to the federal laws of the United States and the laws of the State of Delaware.

     We hereby consent to the reference to us under the heading “Legal Matters” in the joint proxy statement/prospectus forming a part of the Registration Statement and to the filing of this opinion as an exhibit to the Registration Statement, but we do not hereby admit that we are within the class of persons whose consent is required under the provisions of the Securities Act of 1933 or the rules and regulations of the Securities and Exchange Commission issued thereunder.

Very truly yours,
 

/s/ VINSON & ELKINS L.L.P.