Exhibit 3.1

AMENDED AND RESTATED

CERTIFICATE OF FORMATION

OF

ATP OIL & GAS CORPORATION

ATP Oil & Gas Corporation, a Texas corporation (the “Corporation”), by and through the undersigned authorized officer, adopts the following in accordance with Sections 3.057 through 3.060 of the Texas Business Organizations Code (the “TBOC”).

1. The name of the filing entity is ATP Oil & Gas Corporation, a Texas corporation.

2. The Corporation was formed as a for-profit corporation on August 8, 1991, and issued file number 0120230900 by the Secretary of State of the State of Texas (the “Secretary of State”).

3. This instrument restates the entire articles of incorporation of the Corporation, referred to herein as the certificate of formation, as amended and supplemented by all articles of amendment previously issued by the Secretary of State, and as further amended as set forth herein.

4. This instrument further amends the certificate of formation of the Corporation by:

(a) adding a new Article Two indicating that the Corporation is a for-profit corporation and renumbering the following 10 Articles as Articles Three through Twelve and all references thereto accordingly;

(b) amending renumbered Articles Four and Five to replace all references therein to “Texas Business Corporations Act” with “Texas Business Organizations Code”;

(c) amending renumbered Articles Five and Six to replace all references therein to “articles of incorporation” with “certificate of formation”;

(d) amending Section A of renumbered Article Five to add a new paragraph at the end thereof which reads in its entirety as follows:

“As of the date hereof, the Corporation has outstanding two series of Preferred Stock, the designations, preferences and other rights of which are set forth in: (i) the Statement of Designations of Junior Participating Preferred Stock of ATP Oil & Gas Corporation filed with the Secretary of State of the State of Texas on October 14, 2005; and (ii) the Statement of Resolutions Establishing the 8% Convertible Perpetual Preferred Stock of ATP Oil & Gas Corporation filed with the Secretary of State of the State of Texas on September 29, 2009, together with the Articles of Correction filed with the Secretary of State of the State of Texas on October 8, 2009.”

(e) amending Section B(4) of renumbered Article Five to replace the phrase “Upon the effectiveness of this Restated Articles of Incorporation” with the phrase “As of December 12, 2000”; and

(f) amending renumbered Article Eleven to replace the reference to “Article Nine” in the penultimate sentence thereof with “Article Eleven”.

5. Each and every amendment described in paragraph 4 above has been made in accordance with the provisions of the TBOC. The amendments to the certificate of formation and the restated certificate of formation have been approved in the manner required by the TBOC and by the governing documents of the Corporation.

6. The Amended and Restated Certificate of Formation attached hereto as Exhibit A accurately states the text of the certificate of formation being restated and each amendment thereto that is in effect, and as further amended herein. The attached Amended and Restated Certificate of Formation does not contain any other change except for the information permitted to be omitted by the provisions of the TBOC applicable to the Corporation. The existing certificate of formation of the Corporation and all amendments and supplements thereto are hereby superseded by the Amended and Restated Certificate of Formation attached hereto.

7. This document becomes effective when filed by the Secretary of State of the State of Texas.

The undersigned affirms that the person designated as registered agent in the Amended and Restated Certificate of Formation has consented to the appointment. The undersigned signs this document subject to the penalties imposed by law for the submission of a materially false or fraudulent instrument and certifies under penalty of perjury that the undersigned is authorized under the provisions of law governing the Corporation to execute this Amended and Restated Certificate of Formation.

- 2 -

AMENDED AND RESTATED CERTIFICATE OF FORMATION

OF

ATP OIL & GAS CORPORATION

ARTICLE ONE

The name of the corporation is ATP Oil & Gas Corporation.

ARTICLE TWO

ATP Oil & Gas Corporation is a for-profit corporation.

ARTICLE THREE

The period of its duration is perpetual.

ARTICLE FOUR

The purpose or purposes for which the corporation is organized is the transaction of any or all lawful business for which corporations may be incorporated under the Texas Business Organizations Code, as amended.

ARTICLE FIVE

The aggregate number of shares of capital stock which the corporation shall have authority to issue is one hundred ten million (110,000,000) shares, of which one hundred million (100,000,000) shares shall be designated as Common Stock, par value $.001 per share and ten million (10,000,000) shares shall be designated as Preferred Stock, par value $.001 per share.

The following is a statement fixing certain of the designations and rights, voting rights, preferences, and relative, participating, optional or other rights of the Preferred Stock and the Common Stock of the corporation, and the qualifications, limitations or restrictions thereof, and the authority with respect thereto expressly granted to the Board of Directors of the corporation to fix any such provisions not fixed by the certificate of formation:

The Board of Directors is hereby expressly vested with the authority to adopt a resolution or resolutions providing for the issuance of authorized but unissued shares of Preferred Stock, which shares may be issued from time to time in one or more series and in such amounts as may be determined by the Board of Directors in such resolution or resolutions. The rights, voting rights, designations, preferences, and relative, participating, optional or other rights, if any, of each series of Preferred Stock and the qualifications, limitations or restrictions, if any, of such preferences and/or rights (collectively the “Series Terms”) shall be such as are stated and expressed in a resolution or resolutions providing for the creation or revision of such Series Terms (a “Preferred Stock Series Resolution”) adopted by the Board of Directors. The Board

shall have the power and authority, to the fullest extent permissible under the Texas Business Organizations Code (the “Act”), as currently in effect or as amended, to determine and establish by a Preferred Stock Series Resolution, the Series Terms of a particular series, including, without limitation, determination of the following:

(1) The number of shares constituting that series and the distinctive designation of that series, or any increase or decease (but not below the number of shares thereof then outstanding) in such number;

(2) The dividend rate on the shares of that series; whether such dividends, if any, shall be cumulative, noncumulative, or partially cumulative and, if cumulative or partially cumulative, the date or dates from which dividends payable on such shares shall accumulate; and the relative rights of priority, if any, of payment of dividends on shares of that series;

(3) Whether that series shall have voting rights, in addition to the voting rights provided by law, and, if so, the terms of such voting rights;

(4) Whether that series shall have conversion privileges with respect to shares of any other class or classes of stock or of any other series of any class of stock, and, if so, the terms and conditions of such conversion, including provision for adjustment of the conversion rate upon occurrence of such events as the Board of Directors shall determine;

(5) Whether the shares of that series shall be redeemable at the option of either the corporation or the holder, and, if so, the terms and conditions of such redemption, including relative rights of priority, if any, of redemption, the date or dates upon or after which they shall be redeemable, provisions regarding redemption notices, and the amount per share payable in case of redemption, which amount may vary under different conditions and at different redemption dates;

(6) Whether the corporation shall have any repurchase obligation with respect to the shares of that series and, if so, the terms and conditions of such obligation, subject, however, to the limitations of the Act;

(7) Whether that series shall have a sinking fund for the redemption or purchase of shares of that series, and, if so, the terms and amount of such sinking fund;

(8) The rights of the shares of that series in the event of voluntary or involuntary liquidation, dissolution or winding up of the corporation, and the relatives rights of priority, if any, of payment of shares of that series;

(9) The conditions or restrictions upon the creation of indebtedness of the corporation or upon the issuance of additional Preferred Stock or other capital stock ranking on a parity therewith, or prior thereto, with respect to dividends or distribution of assets upon liquidation;

(10) The conditions or restrictions with respect to the issuance of payment of dividends upon, or the making of other distributions to, or the acquisition or redemption

- 4 -

of, shares ranking junior to the Preferred Stock or to any series thereof with respect to dividends or distribution of assets upon liquidation;

(11) The relative priority of each series of Preferred Stock in relation to other series of Preferred Stock with respect to dividends or distribution of assets upon liquidation; and

(12) Any other designations, powers, preferences and rights, including, without limitation, any qualifications, limitations or restrictions thereof.

Any of the Series Terms, including voting rights, of any series may be made dependent upon facts ascertainable outside the certificate of formation and the Preferred Stock Series Resolution, provided that the manner in which such facts shall operate upon such Series Terms is clearly and expressly set forth in the certificate of formation or in the Preferred Stock Series Resolution.

Subject to the provisions of this Article Five, shares of one or more series of Preferred Stock may be authorized or issued from time to time as shall be determined by and for such consideration as shall be fixed by the Board of Directors, in an aggregate amount not exceeding the total number of shares of Preferred Stock authorized by the certificate of formation. All shares of any one series of Preferred Stock so designated by the Board of Directors shall be alike in every particular, except that shares of anyone series issued at different times may differ as to the dates from which dividends thereon shall be cumulative.

As of the filing date of this amended and restated certificate of formation, the corporation has outstanding two series of Preferred Stock, the designations, preferences and other rights of which are set forth in: (i) the Statement of Designations of Junior Participating Preferred Stock of ATP Oil & Gas Corporation filed with the Secretary of State of the State of Texas on October 14, 2005; and (ii) the Statement of Resolutions Establishing the 8% Convertible Perpetual Preferred Stock of ATP Oil & Gas Corporation filed with the Secretary of State of the State of Texas on September 29, 2009, together with the Articles of Correction filed with the Secretary of State of the State of Texas on October 8, 2009.

1. Dividends. Subject to the provisions of any Preferred Stock Series Resolution, the Board of Directors may, in its discretion, out of funds legally available for the payment of dividends and at such times and in such manners as determined by the Board of Directors, declare and pay dividends on the Common Stock of the corporation.

No dividend (other than a dividend in capital stock ranking on a parity with the Common Stock or cash in lieu of fractional shares with respect to such stock dividend) shall be declared or paid on any share or shares of any class of stock or series thereof ranking on a parity with the Common Stock in respect of payment of dividends for any dividend period unless there shall have been declared, for the same dividend period, like proportionate dividends on all shares of Common Stock then outstanding

- 5 -

2. Liquidation. In the event of any liquidation, dissolution or winding up of the corporation, whether voluntary or involuntary (each a “Liquidation Event”), after payment or provision for payment of the debts and other liabilities of the corporation and payment or setting aside for payment of any preferential amount due to the holders of any other class or series of stock, the holders of the Common Stock shall be entitled to receive ratably any or all assets remaining to be paid or distributed.

3. Voting Rights. Subject to any special voting rights set forth in any Preferred Stock Series Resolution, the holders of the Common Stock of the corporation shall be entitled at all meetings of shareholders to one vote for each share of such stock held by them.

4. Recapitalization. As of December 12, 2000 (the “Effective Time”), each issued share of Common Stock of the Corporation shall be reclassified; changed and converted into a number of shares of Common Stock equal to the quotient of 1 divided by 1.4; provided, however, that no fractional shares of Common Stock to which any holder of Common Stock would otherwise be entitled pursuant hereto (aggregating for this purpose all of the shares of Common Stock owned of record by such shareholder) shall be issued. Outstanding stock certificates registered in the name of each record holder thereof that, prior to the Effective Time, represented issued shares of Common Stock shall, after the Effective Time, represent a number of whole shares of Common Stock equal to the product of (a) the quotient of 1 divided by 1.4, times (b) the number of shares of Common Stock such certificates represented immediately prior to the Effective Time rounded down to the nearest whole share until such certificates are presented to the Corporation or its transfer agent for transfer or reissue in which event the Corporation or its transfer agent shall issue stock certificates representing the appropriate number of shares of Common Stock.

Whenever reference is made in this Article Five to shares “ranking prior to” another class of stock or “on a parity with” another class of stock, such reference shall mean and include all other shares of the corporation in respect of which the rights of the holders thereof as to the payment of dividends or as to distributions upon a Liquidation Event, as the case may be, are given preference over, or rank on an equality with, as the case may be, the rights of the holders of such other class of stock. Whenever reference is made to shares “ranking junior to” another class of stock, such reference shall mean and include all shares of the corporation in respect of which the rights of the holders thereof as to the payment of dividends or as to distributions upon a Liquidation Event, as the case may be, are junior and subordinate to the rights of the holders of such class of stock.

Except as otherwise provided herein or in any Preferred Stock Series Resolution, each series of Preferred Stock ranks on a parity with each other with respect to the payment of dividends and distributions upon a Liquidation Event, and each ranks prior to the Common Stock with respect to the payment of dividends and distributions upon a Liquidation Event. Common Stock ranks junior to the Preferred Stock with respect to the payment of dividends and distributions upon a Liquidation Event.

- 6 -

For the purposes of Section 2 of Section B of this Article Five and for the purpose of the comparable sections of any Preferred Stock Series Resolution, the merger or consolidation of the corporation into or with any other corporation, or the merger of any other corporation into it, or the sale, lease, or conveyance of all or substantially all the assets, property or business of the corporation, shall not be deemed to be a liquidation, dissolution or winding up of the corporation.

The corporation shall at all times reserve and keep available, out of its authorized but unissued shares of Common Stock or out of shares of Common Stock held in its treasury, the full number of shares of Common Stock into which all shares of any series of Preferred Stock having conversion privileges from time to time outstanding are convertible.

Unless otherwise provided in a Preferred Stock Series Resolution with respect to a particular series of Preferred Stock, all shares of Preferred Stock redeemed or acquired (as a result of conversion or otherwise) shall be retired and restored to the status of authorized but unissued shares.

ARTICLE SIX

An annual meeting of the shareholders shall be held at such times as may be stated or fixed in accordance with the bylaws. Special meetings may only be called (1) by the Chairman of the Board (if any), the President, the Board of Directors, or such other person or persons as may be authorized in the certificate of formation or the bylaws or (2) by the holders of not less than fifty (50) percent of all the shares entitled to vote at the proposed special meeting.

ARTICLE SEVEN

No holder of shares of stock of the corporation shall have any preemptive or other right, except as such rights are expressly provided by contract, to purchase or subscribe for or receive any shares of any class, or series thereof, of stock of the corporation, whether now or hereafter authorized, or any warrants, options, bonds, debentures or other securities convertible into, exchangeable for or carrying any right to purchase any shares of any class, or series thereof, of stock; but such additional shares of stock and such warrants, options, bonds, debentures or other securities convertible into, exchangeable for or carrying any right to purchase any shares of any class, or series thereof, of stock may be issued or disposed of by the Board of Directors to such persons, and on such terms and for such lawful consideration, as in its discretion it shall deem advisable or as to which the corporation shall have by bind contract agreed.

ARTICLE EIGHT

The corporation will not commence business until it has received for the issuance of its shares consideration of the value of One Thousand Dollars ($1,000) consisting of money paid, labor done, or property actually received.

- 7 -

ARTICLE NINE

The address of the corporation’s current registered office is 4600 Post Oak Place, Suite 200, Houston, Texas 77027 and the name of the current registered agent at such address is T. Paul Bulmahn.

ARTICLE TEN

The number of directors of the corporation shall be fixed by, or in the manner provided by, the bylaws. The number of directors constituting the current Board of Directors is nine and the names and addresses of the persons who are to serve as the directors of the corporation until the next annual meeting of the shareholders or until their successors are elected and qualified are:

The right of shareholders to cumulative voting in the election of directors is expressly prohibited.

ARTICLE ELEVEN

A director of the corporation shall not be liable to the corporation or its shareholders for monetary damages for an act or omission in the director’s capacity as a director, except that this Article Eleven does not eliminate or limit the liability of a director to the extent the director is found liable for (i) a breach of the director’s duty of loyalty to the corporation or its shareholders; (ii) an act or omission not in good faith that constitutes a breach of duty of the director to the corporation or an act or omission that involves intentional misconduct or a

- 8 -

knowing violation of the law; (iii) a transaction from which the director received an improper benefit, whether or not the benefit resulted from an action taken within the scope of the director’s office; or (iv) an act or omission for which the liability of a director is expressly provided by an applicable statute. Any repeal or amendment of this Article Eleven by the shareholders of the corporation shall be prospective only and shall not adversely affect any limitation on the liability of a director of the corporation existing at the time of such repeal or amendment. In addition to the circumstances in which the director of the corporation is not liable as set forth in the preceding sentences, the director shall not be liable to the fullest extent permitted by any provisions of the statutes of the State of Texas hereafter enacted that further limits the liability of a director.

ARTICLE TWELVE

The Board of Directors is expressly authorized to adopt, amend and repeal the bylaws. The corporation’s shareholders are hereby expressly prohibited from amending or repealing the bylaws.

- 9 -