Exhibit 5.1

[CAL DIVE LETTERHEAD]

June 29, 2005

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

Gentlemen:

     The undersigned, as Special Counsel for Cal Dive International, Inc., a Minnesota corporation (the “Company”), in connection with the Company’s filing with the Securities and Exchange Commission of a Registration Statement on Form S-8 (the “Registration Statement”) with respect to the registration under the Securities Act of 1933, as amended, of 3,000,000 shares of the Company’s common stock, no par value per share (the “Shares”), to be offered upon the terms and subject to the conditions set forth in the Company’s 2005 Long-term Incentive Plan (the “Plan”).

     In such capacity, I have examined the corporate documents of the Company, including its 2005 Amended and Restated Articles of Incorporation, its Second Amended and Restated By-Laws and resolutions adopted by its Board of Directors and committees thereof. I have also examined the Plan and the Registration Statement, together with the exhibits thereto, and such other documents which I have deemed necessary for the purposes of expressing the opinion contained herein. I have relied on representations made by and certificates of the officers of the Company and public officials with respect to certain facts material to my opinion. I have made no independent investigation regarding such representations and certificates.

     Based upon and subject to the foregoing, I am of the opinion that the Shares have been duly authorized and, when issued in accordance with the terms of the Plan, will be validly issued, fully paid and nonassessable.

     I hereby consent to the filing of this opinion as an exhibit to the Registration Statement.

Very truly yours,

/s/ ANDREW C. BECHER

Andrew C. Becher