EXHIBIT 23.1 CONSENT OF INDEPENDENT PUBLIC ACCOUNTANTS As independent public accountants, we hereby consent to the incorporation by reference in this Registration Statement on Form S-8 of our report dated February 19, 1998 included in Cal Dive International's Annual Report on form 10-K for the year ended December 31, 1997 and to all references to our Firm included in this Registration Statement. /s/ ARTHUR ANDERSEN LLP Houston, Texas April 15, 1998. 9