EXHIBIT 5.1

Vinson & Elkins ATTORNEYS AT LAW VINSON & ELKINS L.L.P. 2300 FIRST CITY TOWER 1001 FANNIN STREET HOUSTON, TEXAS 77002-6760 TELEPHONE (713) 758-2222 FAX (713) 758-2346 www.velaw.com

September 10, 2003

Plains All American Pipeline, L.P.

333 Clay Street, Suite 1600

Houston, Texas 77002

Ladies and Gentlemen:

We have acted as counsel to Plains All American Pipeline, L.P., a Delaware limited partnership (the “Partnership”), Plains AAP, L.P., a Delaware limited partnership and the general partner of the Partnership (the “General Partner”), and Plains All American GP LLC, a Delaware limited liability company and the general partner of the General Partner (“GP LLC”), in connection with the registration under the Securities Act of 1933, as amended (the “Securities Act”) of the offering and sale of up to an aggregate of 3,737,500 common units representing limited partner interests in the Partnership (the “Common Units”).

As the basis for the opinion hereinafter expressed, we examined such statutes, including the Delaware Uniform Revised Limited Partnership Act, corporate records and documents, certificates of corporate and public officials, and other instruments and documents as we deemed necessary or advisable for the purposes of this opinion. In such examination, we assumed the authenticity of all documents submitted to us as originals and the conformity with the original documents of all documents submitted to us as copies.

Based on the foregoing and on such legal considerations as we deem relevant, we are of the opinion that:

1. The Partnership has been duly formed and is validly existing as a limited partnership under the Delaware Revised Uniform Limited Partnership Act.

2. The Common Units, when issued and paid for under the Partnership’s Registration Statement on Form S-3 (the “Registration Statement”), relating to the Common Units, will be duly authorized, validly issued, fully paid and nonassessable.

We hereby consent to the reference to us under the heading “Legal Matters” in the prospectus forming a part of the Registration Statement and to the filing of this opinion as an exhibit to the Registration Statement, but we do not thereby admit that we are within the class of persons whose consent is required under the provisions of the Securities Act or the rules and regulations of the Securities and Exchange Commission issued thereunder.

Very truly yours,

/s/ VINSON & ELKINS L.L.P.

VINSON & ELKINS L.L.P.