Exhibit 5.1

Fulbright & Jaworski l.l.p.
A Registered Limited Liability Partnership
Fulbright Tower
1301 McKinney, Suite 5100
Houston, Texas 77010-3095
www.fulbright.com

telephone: (713) 651-5151 facsimile: (713) 651-5246

May 26, 2005

Cal Dive International, Inc.
400 N. Sam Houston Parkway E.
Suite 400
Houston, Texas 77060

Gentlemen:

     We have acted as counsel to Cal Dive International, Inc., a Minnesota corporation (the “Registrant”), in connection with the registration under the Securities Act of 1933 of $300,000,000 principal amount of the Registrant’s 3.25% Convertible Senior Notes due 2025 (the “Notes”) and 6,651,885 shares of the Registrant’s common stock, no par value per share, which may be issued upon conversion of the Notes (the “Shares”), as described in the Registrant’s Registration Statement on Form S-3 filed with the Securities and Exchange Commission with respect to the Notes and the Shares (the “Registration Statement”).

     In connection therewith, we have examined the Registration Statement, originals or copies certified or otherwise identified to our satisfaction of the articles of incorporation and by-laws of the Registrant as in effect on the date of issuance of the Notes, the 2005 Amended and Restated Articles of Incorporation of the Registrant, the Second Amended and Restated By-laws of the Registrant, the corporate proceedings with respect to the offering of the Notes, communications of public officials and such other documents and instruments as we have deemed necessary or appropriate for the expression of the opinions contained herein. We have assumed the authenticity and completeness of all records, certificates and other instruments submitted to us as originals, the conformity to original documents of all records, certificates and other instruments submitted to us as copies, the authenticity and completeness of the originals of those records, certificates and other instruments submitted to us as copies and the correctness of all statements of fact contained in all records, certificates and other instruments that we have examined.

     Based upon the foregoing, and having regard for such legal considerations as we deem relevant, we are of the opinion that the Notes have been duly authorized and constitute valid and binding obligations of the Registrant, enforceable against the Registrant in accordance with their respective terms and entitled to the benefits provided by the Indenture, except (a) as such enforceability may be limited by bankruptcy, insolvency, reorganization, fraudulent conveyance, moratorium or other laws affecting creditors’ rights generally and (b) that the remedy of specific performance and injunctive and other forms of equitable relief are subject to certain equitable defenses and to the discretion of the court before which any proceeding therefor may be brought.

May 26, 2005
Page 2

     The opinions expressed herein relate solely to, are based solely upon and are limited exclusively to the laws of the State of New York and the federal laws of the United States of America, to the extent applicable. We hereby consent to the filing of this opinion as an exhibit to the Registration Statement and to the use of our name under the caption “Legal Matters” in the Prospectus included as part of the Registration Statement.

Very truly yours,

/s/ Fulbright & Jaworski L.L.P.

Fulbright & Jaworski L.L.P.