QuickLinks -- Click here to rapidly navigate through this document

EXHIBIT 3.1

AMENDMENT NO. 1 TO THE THIRD AMENDED AND RESTATED
AGREEMENT OF LIMITED PARTNERSHIP OF
PLAINS ALL AMERICAN PIPELINE, L.P.

        THIS AMENDMENT NO. 1 TO THE THIRD AMENDED AND RESTATED AGREEMENT OF LIMITED PARTNERSHIP OF PLAINS ALL AMERICAN PIPELINE, L.P. (this "Amendment"), dated as of April 15, 2004, is entered into and effectuated by Plains AAP, L.P., a Delaware limited partnership, as the General Partner, pursuant to authority granted to it in Section 5.6 of the Third Amended and Restated Agreement of Limited Partnership of Plains All American Pipeline, L.P., dated as of June 27, 2001, as amended (the "Partnership Agreement"). Capitalized terms used but not defined herein are used as defined in the Partnership Agreement.

        WHEREAS, Section 5.6 of the Partnership Agreement provides that the General Partner, without the approval of any Limited Partners, may issue additional Partnership Securities, or classes or series thereof, for any Partnership purpose at any time and from time to time, and may issue such Partnership Securities to such Persons, for such consideration and on such terms and conditions as shall be established by the General Partner in its sole discretion; and

        WHEREAS, Section 13.1 of the Partnership Agreement provides that the General Partner, without the approval of any Partner (subject to the provisions of Section 5.7 of the Partnership Agreement), may amend any provision of the Partnership Agreement necessary or advisable in connection with the authorization of issuance of any class or series of Partnership Securities pursuant to Section 5.6 of the Partnership Agreement; and

        WHEREAS, the General Partner deems it in the best interest of the Partnership to effect this Amendment in order to provide for the issuance of the Class C Common Units to each of Kayne Anderson Energy Fund II, L.P., KAFU Holdings, L.P., Kayne Anderson Capital Income Partners (QP), L.P., Kayne Anderson MLP Fund, L.P., Tortoise Energy Infrastructure Corporation and Vulcan Energy II Inc. (the "Purchasers") pursuant to that certain Class C Common Unit Purchase Agreement, dated March 31, 2004, among the Partnership and each of the Purchasers;

        NOW, THEREFORE, the Partnership Agreement is hereby amended as follows:

1.

Section 4.4(a) is hereby amended and replaced in its entirety as follows:

        (a)   The term "transfer," when used in this Agreement with respect to a Partnership Interest, shall be deemed to refer to a transaction (i) by which the General Partner assigns its General Partner Interest to another Person who becomes the General Partner, and includes a sale, assignment, gift, pledge, encumbrance, hypothecation, mortgage, exchange or any other disposition by law or otherwise or (ii) by which the holder of a Limited Partner Interest assigns such Limited Partner Interest to another Person who is or becomes a Limited Partner or an Assignee, and includes a sale, assignment, gift, exchange or any other disposition by law or otherwise, including any transfer upon foreclosure of any pledge, encumbrance, hypothecation or mortgage.

2.

Article V is hereby amended to add a new Section 5.13 creating a new series of Units as follows:

        (a)   There is hereby created a series of Units to be designated as "Class C Common Units," consisting of Class C Common Units and having the following terms and conditions:

        (i)    Subject to the provisions of Section 6.1(d)(iii)(A), all allocations of items of Partnership income, gain, loss, deduction and credit under Section 6.1 shall be allocated to the Class C Common Units on a basis that is pro rata with the Common Units, so that the amount thereof allocated to each Common Unit will equal the amount thereof allocated to each Class C Common Unit;

        (ii)   Except as provided in paragraph (f) of this Section 5.13, the Class C Common Units shall have the right to share in partnership distributions on a pro rata basis with the Common Units, so

that the amount of any Partnership distribution to each Common Unit will equal the amount of such distribution to each Class C Common Unit;

        (iii)  The Class C Common Units shall have rights upon dissolution and liquidation of the Partnership, including the right to share in any liquidating distributions, that are pro rata with the Common Units, so that the amount of any liquidating distribution to each Common Unit will equal the amount of such distribution to each Class C Common Unit;

        (iv)  The Class C Common Units will not have the privilege of conversion except as provided in paragraphs (c) or (d) of this Section 5.13;

        (v)   The Class C Common Units will have voting rights that are identical to the voting rights of the Common Units and will vote with the Common Units as a single class, so that each Class C Common Unit will be entitled to one vote on each matter with respect to which each Common Unit is entitled to vote, and shall not be deemed outstanding for purposes of determining a quorum, with respect to matters in which the requisite vote is determined by New York Stock Exchange rules or New York Stock Exchange staff interpretations of such rules for listing of the Common Units; each reference in the Partnership Agreement to a vote of holders of Common Units shall be deemed to include a reference to the holders of Class C Common Units;

        (vi)  The Class C Common Units will be evidenced by certificates in such form as the General Partner may approve and, subject to the satisfaction of any applicable legal and regulatory requirements, may be assigned or transferred in a manner identical to the assignment and transfer of other Units; the General Partner will act as registrar and transfer agent for the Class C Common Units; and

        (vii) Except as otherwise provided in the Partnership Agreement and unless the context otherwise requires, for purposes of allocations referred to in paragraph (a)(i), the right to share in Partnership distributions referred to in paragraph (a)(ii), rights upon dissolution and liquidation referred to in paragraph (a)(iii), and voting rights referred to in paragraph (a)(v), and for all other purposes, the Class C Common Units and the Common Units shall be considered as a single class of Units, each Class C Common Unit shall be treated in a manner that is identical, in all respects, to each Common Unit, and each reference in the Partnership Agreement to Common Units shall also be deemed to be a reference to Class C Common Units.

        (b)   [Intentionally Omitted]

        (c)   At any time after six months from the date on which any Class C Common Units are issued, upon written notice to the General Partner, any holder of Class C Common Units will have the right to require the Partnership to use its reasonable best efforts to submit to a vote or consent of the holders of Partnership Securities the approval of a change in the terms of the Class C Common Units to provide that each Class C Common Unit is convertible into one Common Unit at the option of the holder of such Class C Common Unit, such conversion option to be exercisable by any holder of Class C Common Units in whole or in part at any time and from time to time; provided, however, that at any time after six months from the date on which any Class C Common Units are issued, written notice given pursuant to Section 5.12(c) shall also constitute written notice under this Section 5.13(c). The vote or consent required for such change will be the requisite vote required, under New York Stock Exchange rules or New York Stock Exchange staff interpretations of such rules, for listing of the Common Units that would be issued upon any such conversion. Upon receipt of the required vote or consent, the terms of the Class C Common Units will be changed so that they become convertible as described above.

        (d)   Before any holder of Class C Common Units shall be entitled to convert such holder's Class C Common Units into Common Units, he shall surrender the Class C Common Unit Certificates therefor, duly endorsed, at the office of the General Partner or of any transfer agent for the Class C

2

Common units. In the case of any such conversion, the Partnership shall, as soon as practicable thereafter, issue and deliver at such office to such holder of Class C Common Units one or more Common Unit Certificates, registered in the name of such holder, for the number of Common Units to which he shall be entitled as aforesaid. Such conversion shall be deemed to have been made as of the date of the surrender of the Class C Common Units to be converted, and the person entitled to receive the Common Units issuable upon such conversion shall be treated for all purposes as the record holder of such Common Units on said date.

        (e)   If at any time the rules of the New York Stock Exchange or the New York Stock Exchange staff interpretations of such rules are changed so that no vote or consent of holders of Partnership Securities is required as a condition to the listing of the Common Units that would be issued upon such conversion, the terms of the Class C Common Units will be changed so that each Class C Common Unit is convertible (without any vote of any securityholders of the Partnership) into one Common Unit at the option of the holder thereof, such conversion option to be exercisable by any holder of Class C Common Units in whole or in part at any time and from time to time.

        (f)    In the event that (i) any holder of Class C Common Units requires the Partnership to submit to a vote or consent of its holders of Partnership Securities the approval of a change in the terms of the Class C Common Units to provide that they are convertible as provided in Section 5.13(c) above, and (ii) the holders of Partnership Securities do not approve such change by the requisite vote within 120 days after the notice given pursuant to Section 5.13(c), then the terms of the Class C Common Units will be changed so that each Class C Common Unit will become entitled to receive quarterly cash distributions in an amount equal to 110% of the quarterly cash distribution amount payable with respect to each Common Unit; provided, further, that if the holders of Partnership Securities do not approve such change by the requisite vote within 210 days after the notice given pursuant to Section 5.13(c), each Class C Common Unit will become entitled to receive quarterly cash distributions equal to 115% of the quarterly cash distribution payable with respect to each Common Unit. Notwithstanding the foregoing, in no such case shall any holder of Class C Common Units have the right to convert its Class C Common Units unless such holder and its affiliates voted their Partnership Securities for approval of the change requested in Section 5.13(c) (if and to the extent that such Partnership Securities were entitled to be voted).

3

        IN WITNESS WHEREOF, this Amendment has been executed as of the date first written above.

PLAINS AAP, L.P.
By:	PLAINS ALL AMERICAN GP LLC, its General Partner
By:	/s/ Tim Moore
Name:	Tim Moore
Title:	Vice President

4

QuickLinks

EXHIBIT 3.1

AMENDMENT NO. 1 TO THE THIRD AMENDED AND RESTATED AGREEMENT OF LIMITED PARTNERSHIP OF PLAINS ALL AMERICAN PIPELINE, L.P.