Exhibit 5.1

[Gibson, Dunn & Crutcher LLP Letterhead]

Client: 97394-00163

August 7, 2013

Williams Partners L.P.

One Williams Center

Tulsa, Oklahoma 74172

Re: Williams Partners L.P. Public Offering of Common Units

Ladies and Gentlemen:

We have examined the Registration Statement on Form S-3 (File No. 333-179471) (the “Registration Statement”), of Williams Partners L.P., a Delaware limited partnership (the “Company”), filed with the Securities and Exchange Commission (the “Commission”) pursuant to the Securities Act of 1933, as amended (the “Securities Act”), and the prospectus and prospectus supplement (the “Prospectus Supplement”) with respect thereto, dated February 10, 2012, and August 2, 2013, respectively, in connection with the offering by the Company of up to 24,725,000 common units representing limited partner interests (the “Units”). The Units will be issued pursuant to the Underwriting Agreement, dated as of August 2, 2013 (the “Underwriting Agreement”) among the Company, Williams Partners GP LLC, a Delaware limited liability company, and the underwriter named therein (the “Underwriter”).

In arriving at the opinions expressed below, we have examined originals, or copies certified or otherwise identified to our satisfaction as being true and complete copies of the originals, of such documents, records, certificates of officers of the Company and of public officials and other instruments as we have deemed necessary or advisable to enable us to render the opinions set forth below. In our examination, we have assumed without independent investigation the genuineness of all signatures, the legal capacity and competency of all natural persons, the authenticity of all documents submitted to us as originals and the conformity to original documents of all documents submitted to us as copies.

Based upon the foregoing, and subject to the assumptions, exceptions, qualifications and limitations set forth herein, we are of the opinion that:

1. The Units, when issued and delivered to and paid for by the Underwriter in accordance with the terms of the Underwriting Agreement, will be validly issued.

2. Purchasers of the Units will have no obligation to make payments to the Company or its creditors (other than the purchase price for the Units) or contributions to the Company or its creditors solely by reason of the purchasers’ ownership of the Units.

The opinions set forth herein are subject to the following assumptions, qualifications, limitations and exceptions:

August 7, 2013

Page 2

A. The effectiveness of the Registration Statement under the Securities Act will not have been terminated or rescinded.

B. We render no opinion herein as to matters involving any laws other than the Delaware Revised Uniform Limited Partnership Act (the “Delaware LP Act”) and the Delaware Limited Liability Company Act (the “Delaware LLC Act”). This opinion is limited to the effect of the current state of the Delaware LP Act and the Delaware LLC Act and the facts as they currently exist. We assume no obligation to revise or supplement this opinion in the event of future changes in such laws or the interpretations thereof or such facts.

We consent to the filing of this opinion as an exhibit to the Registration Statement, and we further consent to the use of our name under the caption “Legal Matters” in the Prospectus Supplement. In giving these consents, we do not thereby 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.

Very truly yours,

/s/ Gibson, Dunn & Crutcher LLP