QuickLinks -- Click here to rapidly navigate through this document

Exhibit 5.1

September 25, 2015

Plains All American Pipeline, L.P.
333 Clay Street, Suite 1600
Houston, Texas 77002

Ladies and Gentlemen:

        We have acted as counsel for Plains All American Pipeline, L.P., a Delaware limited partnership (the "Partnership"), with respect to the preparation of the Registration Statement on Form S-3 (the "Registration Statement") filed on the date hereof with the Securities and Exchange Commission (the "Commission") in connection with the registration by the Partnership under the Securities Act of 1933, as amended (the "Securities Act"), of the offer and sale by the Partnership from time to time, pursuant to Rule 415 under the Securities Act, of:

        (1)   common units representing limited partner interests in the Partnership (the "Common Units"); and

        (2)   debt securities, which may be co-issued by PAA Finance Corp., a Delaware corporation ("PAA Finance"), in one or more series, consisting of notes, debentures or other evidences of indebtedness (the "Debt Securities").

        The Common Units and Debt Securities are collectively referred to herein as the "Securities." We have also participated in the preparation of the Prospectus (the "Prospectus") contained in the Registration Statement to which this opinion is an exhibit.

        In rendering the opinions set forth below, we have examined and relied upon (i) the Delaware Revised Uniform Limited Partnership Act (the "Delaware LP Act"), (ii) Delaware General Corporation Law (the "DGCL"), (iii) the Registration Statement, including the Prospectus, (iv) the Senior Indenture (the "Senior Indenture"), attached as Exhibit 4.1 to the Registration Statement, (v) the form of Subordinated Indenture (the "Subordinated Indenture," together with the Senior Indenture, the "Indentures"), attached as Exhibit 4.2 to the Registration Statement, (vi) the Fourth Amended and Restated Agreement of Limited Partnership of the Partnership, as amended, (vii) the Certificate of Limited Partnership filed with the Secretary of State of Delaware pursuant to the Delaware LP Act in connection with the formation of the Partnership, (viii) the bylaws and certificate of incorporation of PAA Finance, and (ix) such other certificates, statutes and other instruments and documents as we consider appropriate for purposes of the opinions hereafter expressed. In addition, we have reviewed such questions of law as we consider appropriate.

        In connection with this opinion, we have assumed that:

        (1)   the Registration Statement, and any amendments thereto (including post-effective amendments), will have become effective;

        (2)   a Prospectus Supplement will have been prepared and filed with the Commission describing the Securities offered thereby;

        (3)   all Securities will be issued and sold in compliance with applicable federal and state securities laws and in the manner stated in the Registration Statement and the appropriate Prospectus Supplement;

September 25, 2016 Page 2

        (4)   a definitive purchase, underwriting or similar agreement with respect to any Securities offered will have been duly authorized and validly executed and delivered by the Partnership and the other parties thereto; and

        (5)   any Securities issuable upon conversion, exchange or exercise of any Security being offered will be duly authorized, created, and, if appropriate, reserved for issuance upon such conversion, exercise or exchange.

        Based upon and subject to the foregoing, we are of the opinion that:

        (1)   With respect to the Common Units, when (i) the Partnership has taken all necessary action to approve the issuance of such Common Units, the terms of the offering thereof and related matters; and (ii) the Common Units have been issued and delivered in accordance with the terms of the applicable definitive purchase, underwriting or similar agreement approved by the Partnership upon payment of the consideration thereof or provided for therein, then the Common Units will be validly issued, fully paid and non-assessable.

        (2)   With respect to the Debt Securities, when (i) the applicable Indenture has been duly qualified under the Trust Indenture Act of 1939, as amended; (ii) the Partnership and PAA Finance, as applicable, have taken all necessary action to duly authorize and approve the issuance and terms of such Debt Securities, the terms of the offering thereof and related matters; and (iii) such Debt Securities have been duly authorized, executed, authenticated, issued and delivered in accordance with the provisions of the applicable Indenture and the applicable definitive purchase, underwriting or similar agreement approved by the Partnership and PAA Finance, as applicable, upon payment of the consideration thereof or provided for therein, such Debt Securities will be legally issued and will constitute valid and legally binding obligations of the Partnership and PAA Finance, as applicable, enforceable against the Partnership and PAA Finance, as applicable, in accordance with their terms, except as such enforcement may be limited by (x) applicable bankruptcy, insolvency, fraudulent transfer, reorganization, moratorium or similar laws from time to time in effect affecting creditors' rights and remedies generally and general principles of equity (regardless of whether such principles are considered in a proceeding in equity or at law) and (y) public policy, applicable law relating to fiduciary duties and indemnification and an implied covenant of good faith and fair dealing.

        The opinions expressed herein are qualified in the following respects:

        (1)   As to any facts material to the opinion contained herein, we have made no independent investigation of such facts and have relied, to the extent that we deem such reliance proper, upon certificates of public officials and officers or other representatives of the general partner of the Partnership and the Partnership.

        (2)   We have assumed, without independent verification, that the certificates for the Common Units will conform to the specimens thereof examined by us and will have been duly countersigned by a transfer agent and duly registered by a registrar of the Common Units.

        (3)   We have assumed that (i) all information contained in all documents submitted to us for review is accurate and complete, (ii) each such document submitted to us as an original is authentic and each such document submitted to us as a copy conforms to an authentic original of such document, (iii) all signatures on each such document examined by us are genuine, and (iv) each certificate from governmental officials reviewed by us is accurate, complete and authentic, and all official public records are accurate and complete.

        (4)   We express no opinions concerning (i) the validity or enforceability of any provisions contained in the Indentures that purport to waive or not give effect to rights to notices, defenses, subrogation or other rights or benefits that cannot be effectively waived under applicable law; or (ii) the enforceability of indemnification provisions to the extent they purport to relate to liabilities resulting from or based upon negligence or any violation of federal or state securities or blue sky laws.

September 25, 2016 Page 3

        (5)   This opinion is limited in all respects to U.S. federal laws, the laws of the State of New York, the Delaware LP Act and the DGCL.

        We hereby consent to the references to this firm under the caption "Legal Matters" in the Prospectus and to the filing of this opinion as an exhibit to the Registration Statement. By giving such consent, we do not admit that we are within the category of persons whose consent is required under Section 7 of the Securities Act or the rules and regulations of the Commission issued thereunder.

Very truly yours,

/s/ Vinson & Elkins L.L.P.

QuickLinks

Exhibit 5.1