HORIZON OFFSHORE, INC. CERTIFICATE OF DESIGNATION, PREFERENCES AND RIGHTS OF SERIES A REDEEMABLE PARTICIPATING PREFERRED STOCK Pursuant to Section 151 of the Delaware General Corporation Law

EXHIBIT 4.1

EXHIBIT A

HORIZON OFFSHORE, INC.

CERTIFICATE OF DESIGNATION,

Pursuant to Section 151 of the

               HORIZON OFFSHORE, INC. (the “Company”), a corporation organized and existing under the laws of the State of Delaware, hereby certifies that pursuant to the provisions of Section 151 of the Delaware General Corporation Law, its Board of Directors, by unanimous written consent, dated November 4, 2004 adopted the following resolution, which resolution remains in full force and effect as of the date hereof:

               WHEREAS, the Board of Directors of the Company is authorized, within the limitations and restrictions stated in the Certificate of Incorporation, to fix by resolution or resolutions the designation of preferred stock and the powers, preferences and relative participating, optional or other special rights and qualifications, limitations or restrictions thereof, including, without limiting the generality of the foregoing, such provisions as may be desired concerning voting, redemption, dividends, dissolution or the distribution of assets, conversion or exchange, and such other subjects or matters as may be fixed by resolution or resolutions of the Board of Directors under the Delaware General Corporation Law; and

               WHEREAS, it is the desire of the Board of Directors of the Company, pursuant to its authority as aforesaid, to authorize and fix the terms of the preferred stock to be designated the Series A Redeemable Participating Preferred Stock of the Company and the number of shares constituting such preferred stock;

               NOW, THEREFORE, BE IT RESOLVED, that there is hereby authorized the Series A Redeemable Participating Preferred Stock on the terms and with the provisions herein set forth:

DESIGNATION, PREFERENCES AND RIGHTS

of

SERIES A REDEEMABLE PARTICIPATING PREFERRED STOCK

of

HORIZON OFFSHORE, INC.

               The relative rights, preferences, powers, qualifications, limitations and restrictions granted to or imposed upon the Series A Redeemable Participating Preferred Stock or the holders thereof are as follows:

               1. Definitions. For purposes of this Certificate of Designation, Preferences and Rights of Series A Redeemable Participating Preferred Stock (this “Certificate of Designation”) the following definitions shall apply:

               “Accretion Rate” shall mean 25% per annum calculated on a 360 day per year basis, based on the actual number of days elapsed.

               “Applicable Fully Diluted Equity Value” shall mean, at any date of determination, (a) (i) the product of (A) the aggregate number of Fully Diluted Outstanding shares of Common Stock and (B) the Current Equity Entitlement Factor multiplied by (ii) the Current Market Price, minus (b) $1,925,000.

               “Appraised Value” shall mean, in respect of any share of Common Stock on any date herein specified, the fair saleable value of such share of Common Stock (determined without giving effect to the discount for (i) a minority interest or (ii) any lack of liquidity of the Common Stock or to the fact that Company may have no class of equity registered under the Exchange Act) as of the last day of the most recent fiscal month to end within 60 days prior to such date specified, based on the value of Company, as determined by an investment banking firm selected by the Company and the Required Holders, divided by the number of Fully Diluted Outstanding shares of Common Stock.

               “Board” shall mean the Board of Directors of the Company.

               “Business Day” shall mean any day other than a Saturday, Sunday, or a day on which banking institutions in the State of New York or the State of Texas are authorized or obligated by law or executive order to close.

               “Common Stock” shall mean the Common Stock, par value $1.00 per share, of the Company, as constituted from time to time; provided however, the Common Stock as constituted from time to time shall have only the voting powers and rights appurtenant to the Common Stock existing at the Original Issue Date.

               “Company” shall mean Horizon Offshore, Inc., a Delaware corporation.

2

               “Current Equity Entitlement Factor” shall mean, at any date of determination, the quotient of (a) the number of shares of Redeemable Preferred Stock issued on the Original Issue Date divided by (b) 10,000, as increased to the date of determination by application of the Accretion Rate, compounded quarterly, for the period commencing six months from the Original Issue Date to the date of determination.

               “Current Market Price,” when used with reference to shares of Common Stock on any date, shall mean the arithmetic average of the daily Weighted Average Price for 20 consecutive Trading Days commencing 30 days before such date, or if there shall not be a public market for such shares, the Appraised Value per share of Common Stock at such date.

               “Event of Default” shall mean the failure of the Company to redeem shares of Redeemable Preferred Stock should it be required or undertake to do so pursuant to Section 6 hereof.

               “Exchange Act” shall mean the Securities Exchange Act of 1934, as amended, or any similar Federal statute, and the rules and regulations of the Securities and Exchange Commission thereunder, all as the same shall be in effect at the time. Reference to a particular section of the Securities Exchange Act of 1934, as amended, shall include reference to the comparable section, if any, of any such similar Federal statute.

               “Fully Diluted Outstanding” shall mean, with reference to Common Stock, at any date as of which the number of shares thereof is to be determined, (a) all shares of Common Stock outstanding at such date, (b) all shares of Common Stock underlying any unexercised warrants issued by the Company to purchasers of the Company’s 16% Subordinated Secured Notes, (c) all Pro Forma Warrant Shares as of such date (calculated with respect to all shares of Redeemable Preferred Stock outstanding at such date), and (d) all shares of Common Stock underlying other options or warrants to purchase, or securities convertible into, shares of Common Stock outstanding on such date excluding any such options, warrants or securities with an exercise or conversion price in excess of the Current Market Price.

               “GAAP” shall mean generally accepted accounting principles in the United States of America as in effect from time to time.

               “Liquidation Preference” shall mean a per share amount for the Redeemable Preferred Stock equal to the quotient of (a) the Applicable Fully Diluted Equity Value divided by (b) the number of outstanding shares of Redeemable Preferred Stock.

               “Notice Period” has the meaning set forth in Section 6(a)(i)(B) of this Certificate of Designation.

3

               “Organic Change” shall mean (a) any sale, lease, exchange or other transfer of all or substantially all of the property and assets of the Company, (b) any liquidation, dissolution or winding up of the Company, whether voluntary or involuntary, (c) any merger or consolidation to which the Company is a party and which the holders of the voting securities of the Company immediately prior thereto own less than a majority of the outstanding voting securities of the surviving entity immediately following such transaction, or (d) any Person or group of Persons (as such term is used in Section 13(d) of the Exchange Act) shall beneficially own (as defined in Rule 13d-3 under the Exchange Act) securities of the Company representing 50% or more of the voting securities of the Company then outstanding, excluding for purposes of this clause (d) any such ownership change which may be deemed to result from the issuance of the shares of Redeemable Preferred Stock on the Original Issue Date or which may result from the issuance of shares of Common Stock to holders of Subordinated Notes pursuant to a Qualified Rights Offering. For purposes of the preceding sentence, “voting securities” shall mean securities, the holders of which are ordinarily, in the absence of contingencies, entitled to elect the corporate directors (or Persons performing similar functions).

               “Original Issue Date” shall mean the date of the original issuance of shares of Redeemable Preferred Stock.

               “Person” shall mean any individual, firm, corporation or other entity, and shall include any successor (by merger or otherwise) of such entity.

               “Pro Forma Warrant Shares” shall mean, at any date of determination, the aggregate number of Warrant Shares purchasable under the number of Warrants that would be required to be issued in redemption of a share of Redeemable Preferred Stock at such date under Section 6(a)(ii)(B), as if such redemption had occurred on such date.

               “Principal Market” shall mean the NASDAQ National Market.

               “Purchase Agreement” shall mean the Purchase Agreement, dated as of November 4, 2004, by and among the Company and the Purchasers named therein, as it may be amended from time to time, a copy of which is on file at the principal office of the Company.

               “Qualified Rights Offering” has the meaning set forth in Section 6(a)(ii)(B).

               “Redeemable Preferred Stock” shall refer to shares of Series A Redeemable Participating Preferred Stock, $1.00 par value per share, of the Company.

               “Redemption Date” shall mean any date on which the shares of Redeemable Preferred Stock are to be redeemed by the Company.

               “Redemption Price” shall mean, at any date of determination, a per share amount equal to the Liquidation Preference thereof at such date.

4

               “Registration Rights Agreement” shall mean the Registration Rights Agreement in the form of Exhibit C attached to the Purchase Agreement.

               “Required Holders” shall mean the holders of at least of a majority of the outstanding shares of Redeemable Preferred Stock.

               “Stockholder Approval” shall mean the approval, by the holders of the requisite number of shares of Common Stock entitled to vote thereon, of the proposal described in Section 6.2 of the Purchase Agreement.

               “Subordinated Notes” shall mean Company’s 16% subordinated secured notes due March 31, 2007 and its 18% subordinated secured notes due March 31, 2007.

               “Subscription Rights” has the meaning set forth in Section 3(b) of this Certificate of Designation.

               “Subsidiary” of any Person shall mean any corporation or other entity of which a majority of the voting power or the voting equity securities or equity interest is owned, directly or indirectly, by such Person.

               “Trading Day” shall mean a Business Day or, if the Common Stock is listed or admitted to trading on any national securities exchange or NASDAQ market, a day on which such exchange or market is open for the transaction of business.

               “Warrant Shares” shall mean the shares of Common Stock from time to time purchasable upon exercise of the Warrants.

               “Warrants” shall mean the Company’s Common Stock purchase warrants, with an initial per share exercise price equal to the quotient of (a) $1,925,000 divided by (b) the aggregate number of Warrants Shares for which such warrants issued in any redemption pursuant to Section 6(a)(ii)(B) and 6(a)(iv) of this Certificate of Designation are exercisable, and each of which warrants shall be issued pursuant to and evidenced by the Warrant Certificate in the form of Exhibit B attached to the Purchase Agreement.

               “Weighted Average Price” shall mean, for any share of Common Stock as of any date, the dollar volume-weighted average price for such Common Stock on the Principal Market during the period beginning at 9:30:01 a.m., New York City time (or such other time as the Principal Market publicly announces is the official open of trading), and ending at 4:00:00 p.m., New York City time (or such other time as the Principal Market publicly announces is the official close of trading) as reported by Bloomberg through its “Volume at Price” functions, or, if the foregoing does not apply, the dollar volume/weighted average price of such Common Stock in the over-the-counter market on the electronic bulletin board for such Common Stock during the period beginning at 9:30:01 a.m., New York City time (or such other time as the Principal Market publicly announces is the official open of trading), and ending at 4:00:00 p.m., New York City time (or such other time as the Principal Market publicly announces is the

5

official close of trading) as reported by Bloomberg, or, if no dollar/volume weighted average price is reported for the Common Stock by Bloomberg for such hours, the average of the highest closing bid price and the lowest closing ask price of any of the market makers for such Common Stock as reported in the “pink sheets” by Pink Sheets LLC (formerly the National Quotation Bureau, Inc.). All such determinations are to be appropriately adjusted for any stock dividend, stock split, stock combination or other similar transaction during the applicable calculation period.

               2. Designation; Number of Shares. The designation of the preferred stock authorized by this resolution shall be “Series A Redeemable Participating Preferred Stock” and the number of shares of Series A Redeemable Participating Preferred Stock authorized hereby shall be 1,400 shares.

               3. Dividends.

               (a) Except as otherwise provided in Section 3(b), no dividends shall be declared or paid on shares of Redeemable Preferred Stock.

               (b) So long as any shares of Redeemable Preferred Stock shall be outstanding, (i) no dividend whatsoever shall be paid or declared, and no distribution shall be made, on account of any Common Stock unless an equivalent additional dividend or distribution is simultaneously paid on the Redeemable Preferred Stock based on the number of Pro Forma Warrant Shares which it then represents and (ii) no shares of Common Stock shall be purchased, redeemed or acquired by the Company and no funds shall be paid into or set aside or made available for a sinking fund for the purchase, redemption or acquisition thereof. Notwithstanding the foregoing subclause (i), the holders of Redeemable Preferred Stock shall not be entitled to receive any dividend or distribution paid in shares of Common Stock, or options or warrants to purchase shares of Common Stock or subscription or purchase rights to acquire for a cash purchase price newly issued shares of Common Stock effected as a distribution on all outstanding shares of Common Stock (“Subscription Rights”).

               4. Liquidation Rights of Redeemable Preferred Stock.

               (a) In the event of any liquidation, dissolution or winding up of the Company, whether voluntary or involuntary, the holders of Redeemable Preferred Stock then outstanding shall be entitled to be paid out of the assets of the Company available for distribution to its stockholders, whether such assets are capital, surplus or earnings, before any payment or declaration and setting apart for payment of any amount shall be made in respect of any shares of Common Stock or any share of any other class or series of the Company’s preferred stock ranking junior to the Redeemable Preferred Stock with respect to the payment of dividends or distribution of assets on liquidation, dissolution or winding up of the Company, an amount in cash equal to the Liquidation Preference plus all declared or accrued and unpaid dividends.

6

               (b) If upon any liquidation, dissolution or winding up of the Company, whether voluntary or involuntary, the assets to be distributed among the holders of Redeemable Preferred Stock shall be insufficient to permit the payment to such stockholders of the full preferential amounts aforesaid, then the entire assets of the Company to be distributed shall be distributed ratably among the holders of Redeemable Preferred Stock, based on the full preferential amounts for the number of shares of Redeemable Preferred Stock held by each holder.

               (c) After payment to the holders of Redeemable Preferred Stock of the amounts set forth in Section 4(a) hereof, the entire remaining assets and funds of the Company legally available for distribution, if any, shall be distributed among the holders of any Company stock entitled to a preference over the Common Stock in accordance with the terms thereof and, thereafter, to the holders of Common Stock.

               5. Voting Rights. Holders of Redeemable Preferred Stock shall have no voting rights, except as provided by law; provided, however, that the affirmative vote of the Required Holders, voting together as a class, in person or by proxy, at a special or annual meeting of such holders called for the purpose, or pursuant to a written consent of such holders shall be necessary to:

               (a) authorize, adopt or approve an amendment or alteration to, or repeal of, the Certificate of Incorporation of the Company (whether pursuant to Section 242 or 251(e) of the Delaware General Corporation Law, merger, consolidation or otherwise) which would alter or change in any manner the terms, powers, preferences or special rights of the shares of the Redeemable Preferred Stock or grant waivers thereof, or which would otherwise adversely affect the rights of the Redeemable Preferred Stock, provided that no such modification or amendment may, without the consent of each holder of Redeemable Preferred Stock affected thereby, (i) change any Redemption Date; (ii) reduce the Liquidation Preference, Accretion Rate or Redemption Price of the Redeemable Preferred Stock; or (iii) reduce the percentage of outstanding Redeemable Preferred Stock necessary to modify or amend the terms thereof or to grant waivers thereof; or

               (b) issue any shares of the capital stock of the Company ranking senior to, or pari passu with, or junior to (either as to dividends or upon voluntary or involuntary liquidation, dissolution or winding up) the Redeemable Preferred Stock, or issue any securities convertible into or exchangeable for such shares, except shares of Common Stock.

               6. Redemption of Redeemable Preferred Stock.

               (a) (i) Optional Redemption.

     (A) If any Organic Change occurs, at the option of any holder of outstanding Redeemable Preferred Stock (as exercised pursuant to Section 6(a)(i)(B) below), the Company shall redeem,

7

for cash at the Redemption Price, those outstanding shares of Redeemable Preferred Stock which the holders of such Redeemable Preferred Stock have elected to redeem, such redemption to occur immediately prior to or simultaneously with the consummation of such Organic Change. If the Required Holders so elect in connection with such Organic Change by written notice to the Company within the Notice Period referred to below, the Company shall redeem all of the outstanding shares of Redeemable Preferred Stock.

     (B) The Company will give written notice of any Organic Change, stating the substance and intended date of consummation thereof, not more than sixty (60) Business Days nor fewer than forty (40) Business Days prior to the date of consummation thereof, to each holder of Redeemable Preferred Stock. The holders of the Redeemable Preferred Stock shall have thirty-five (35) Business Days (the “Notice Period”) from the date of the receipt of such notice to demand (by written notice mailed to the Company) redemption of all or any portion of the shares of Redeemable Preferred Stock held by such holder. If, by the expiration of the Notice Period, the Required Holders have so elected to demand redemption of all of the outstanding shares of Redeemable Preferred Stock as provided in Section 6(a)(i)(A) above, the Company shall give prompt written notice of such election to each other holder of Redeemable Preferred Stock within five (5) Business Days after the expiration of the Notice Period.

(ii) Mandatory Redemption.

     (A) The Company shall redeem, and the holders of the outstanding Redeemable Preferred Stock shall sell to the Company, for cash at the Redemption Price, all of the outstanding Redeemable Preferred Stock on the sixth anniversary of the Original Issue Date.

     (B) If the Stockholder Approval is obtained, the Company shall redeem, and the holders of the outstanding Redeemable Preferred Stock shall surrender, transfer and assign to the Company, for the equity consideration described in Section 6(a)(iv) at the Redemption Price, all of the outstanding Redeemable Preferred Stock upon the expiration and closing of any offering of Subscription Rights by the Company to the holders of its Common Stock, pursuant to which shares of Common Stock offered for purchase thereunder shall have been issued and sold to stockholders subscribing therefor for aggregate net proceeds of at least $65,000,000, or to the extent such shares are not issued and

8

sold thereunder, holders of the Subordinated Notes as standby purchasers shall have exchanged up to $65,000,000 in aggregate principal amount of Subordinated Notes for shares of Common Stock such that the total of such net proceeds so received and aggregate principal amount of Subordinated Notes so exchanged equals $65,000,000 (a “Qualified Rights Offering”).

     (iii) Surrender of Certificates. On or before the Redemption Date, each holder of Redeemable Preferred Stock shall surrender the certificate or certificates representing such shares of Redeemable Preferred Stock to the Company, in the manner and at the place designated in the written notice of redemption provided by the Company, and thereupon the Redemption Price for such shares shall be payable in the manner described in Section 6(a)(iv) on the Redemption Date to the person whose name appears on such certificate or certificates as the owner thereof, and each surrendered certificate shall be cancelled and retired.

     (iv) Payment or Satisfaction of Redemption Price. The Redemption Price shall be payable in cash at the Redemption Date upon any redemption pursuant to Section 6(a)(i)(A) or Section 6(a)(ii)(A). The Company’s obligation to pay the Redemption Price in any redemption under Section 6(a)(ii)(B) shall be satisfied by delivering to each holder in full redemption of all of such holder’s shares of Redeemable Preferred Stock one or more certificates representing Warrants to purchase, in the aggregate, a number of Warrant Shares equal to the product of (A) (1) the number of Fully Diluted Outstanding shares of Common Stock at the Redemption Date multiplied by (2) the Current Equity Entitlement Factor, multiplied by (B) a fraction, the numerator of which is the number of such holder’s shares of Redeemable Preferred Stock called for redemption and the denominator of which is the number of all shares of Redeemable Preferred Stock then outstanding.

     (v) Warrant Certificate. In connection with any issuance of Warrants in redemption of shares of Redeemable Preferred Stock, the Company shall execute and issue a Warrant Certificate to and in favor of each holder in the form of Exhibit B to the Purchase Agreement with the blanks appropriately filled in, and the Company and the holders shall execute and deliver the Registration Rights Agreement.

               (b) Unless there shall occur an Event of Default, the Accretion Rate shall be reduced to zero (0) with respect to any Redeemable Preferred Stock to be redeemed upon and after the Redemption Date, and the holders of shares of Redeemable Preferred Stock which are to be redeemed shall cease to have any further rights with respect thereto on the Redemption Date, other than to receive the applicable Redemption Price, which, in the case of any Redemption Price paid in cash, shall be without interest.

9

               (c) If, at the time of any redemption pursuant to Section 6(a)(i)(A) or Section 6(a)(ii)(A), the funds of the Company legally available for redemption of Redeemable Preferred Stock are insufficient to redeem the number of shares required to be redeemed, those funds which are legally available shall be used to redeem the maximum possible number of such shares, pro rata based upon the number of shares to be redeemed. At any time thereafter when additional funds of the Company become legally available for the redemption of Redeemable Preferred Stock, such funds shall immediately be used to redeem the balance of the shares of Redeemable Preferred Stock which the Company has become obligated to redeem pursuant to this Section 6(c), but which it has not redeemed; or, in the case of a redemption pursuant to Section 6(a)(i) if a person other than the Company is the surviving or resulting corporation in any Organic Change, such person shall, at the consummation of such Organic Change, redeem such balance of the shares of Redeemable Preferred Stock (and the Company shall so provide in its agreements with such person relating to such Organic Change).

               (d) The Company may not otherwise redeem or repurchase the Redeemable Preferred Stock.

               7. Reports as to Liquidation Preference. Not later than the forty-fifth (45^th) day following the end of each fiscal quarter of the Company commencing with the fiscal quarter ended September 30, 2005, the Company shall deliver to each holder of the Redeemable Preferred Stock a certificate signed by the President or a Vice President and by the Treasurer or an Assistant Treasurer or the Secretary or an Assistant Secretary of the Company setting forth the amount of the Liquidation Preference as at the end of such quarter, describing in reasonable detail the method by which such Liquidation Preference was calculated, including without limitation the basis for the calculation of the Applicable Fully Diluted Equity Value as of such date.

               8. Remedies. Any registered holder of Redeemable Preferred Stock may proceed to protect and enforce its rights and the rights of such holders by any available remedy by proceeding at law or in equity to protect and enforce any such rights, whether for the specific enforcement of any provision in this Certificate of Designation or in aid of the exercise of any power granted herein, or to enforce any other proper remedy.

               9. No Reissuance of Redeemable Preferred Stock. No Redeemable Preferred Stock acquired by the Company by reason of redemption, purchase, or otherwise shall be reissued, and all such shares shall be cancelled, retired and eliminated from the shares which the Company shall be authorized to issue.

               10. Dispute Resolution. In the case of a dispute as to the determination of the Weighted Average Price, the Redemption Price or any arithmetic calculation required pursuant to this Certificate of Designation, the Company shall submit the disputed determinations or arithmetic calculations via facsimile within five Business Days of the notice of redemption or other event giving rise to such dispute, as the case may be, to each Holder. If the Required Holders and the Company are unable to agree upon such determination or calculation, as applicable, within three Business Days of such disputed

10

determination or calculation being submitted to the Holders, then the Company shall, within three Business Days, submit via facsimile the disputed determination or arithmetic calculation to an independent, reputable investment bank selected by the Company and approved by the Required Holders. The Company, at the Company’s expense, shall use its reasonable best efforts to cause the investment bank to perform the determinations or calculations and notify the Company and each Holder of the results no later than five Business Days from the time it receives the disputed determinations or calculations. Such investment bank’s determination or calculation, as the case may be, shall be binding upon all parties absent demonstrable error.

               11. Notices. All notices to the Company permitted hereunder shall be personally delivered or sent by first class mail, postage prepaid, addressed to its principal office located at 2500 CityWest Boulevard, Suite 2200, Houston, Texas 77042, or to such other address at which its principal office is located and as to which notice thereof is similarly given to the holders of the Redeemable Preferred Stock at their addresses appearing on the books of the Company.

[Remainder of Page Intentionally Left Blank]

11

               IN WITNESS WHEREOF, Horizon Offshore, Inc. has caused this Certificate to be signed by its President and Secretary, respectively, on this 4^th day of November, 2004.

Signature Page