1
                                                                     EXHIBIT 5.1

                       [VINSON & ELKINS L.L.P. LETTERHEAD]



                                December 13, 2000


Stone Energy Corporation
625 East Kaliste Saloom Road
Lafayette, Louisiana 70508

RE:  Registration Statement on Form S-4 of Stone Energy Corporation

Ladies and Gentlemen:

         We have acted as counsel to Stone Energy Corporation, a Delaware
corporation ("Stone"), in connection with the preparation of the registration
statement on Form S-4 (the "Registration Statement"), filed with the Securities
and Exchange Commission (the "Commission") under the Securities Act of 1933, as
amended (the "Act"), with respect to the shares of Stone common stock, par value
$0.01 per share (the "Stone Common Stock"), proposed to be issued in connection
with the merger (the "Merger") of Partner Acquisition Corp., a Delaware
corporation and a wholly-owned subsidiary of Stone ("Sub"), with and into Basin
Exploration, Inc., a Delaware corporation ("Basin"), upon the terms and subject
to the conditions of the Agreement and Plan of Merger, dated as of October 28,
2000, among Stone, Sub and Basin (the "Merger Agreement").

         We have examined originals or copies, certified or otherwise,
identified to our satisfaction, of the Certificate of Incorporation and Restated
Bylaws of Stone, each as amended to the date hereof, and such other
certificates, statutes and other instruments and documents as we considered
appropriate for purposes of the opinions hereafter expressed.

         In connection with this opinion, we have assumed that (i) the
Registration Statement, and any amendment thereto (including post-effective
amendments), will have become effective under the Act, (ii) the requisite vote
by Stone stockholders is obtained regarding the amendment of Stone's Certificate
of Incorporation to increase the authorized shares of Stone Common Stock and
regarding the issuance of the Stone Common Stock in connection with the Merger,
(iii) the requisite vote by Basin stockholders is obtained regarding adoption of
the Merger Agreement, and (iv) the proper filing of the Certificate of Merger
with the Secretary of State of the State of Delaware.



   2
Page 2
December 13, 2000


         Based on the foregoing, we are of the opinion that:

         1. Stone has been duly incorporated and is validly existing and in good
standing under the laws of the State of Delaware.

         2. The Stone Common Stock being registered under the Registration
Statement, when issued in connection with the Merger as contemplated by the
Merger Agreement, will be duly authorized, validly issued, fully paid and
non-assessable.

         The forgoing opinions are limited in all respects to the federal laws
of the United States and the General Corporation Law of the State of Delaware.

         We hereby consent to the filing of this opinion as an exhibit to the
Registration Statement and to the reference to this firm under the caption
"Legal and Tax Matters" in the Registration Statement. By giving such consent,
we do not admit 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 issued thereunder.

                                Very truly yours,

                                VINSON & ELKINS L.L.P.