Exhibit 5.1

October 30, 2017

BP Midstream Partners LP

501 Westlake Park Boulevard

Houston, Texas 77079

Ladies and Gentlemen:

We have acted as counsel for BP Midstream Partners LP, a Delaware limited partnership (the “Partnership”), in connection with the Partnership’s registration under the Securities Act of 1933, as amended (the “Act”), of the offer and sale of an aggregate of up to 5,761,308 of the Partnership’s common units, which represent limited partner interests (the “Units”), pursuant to the Partnership’s registration statement on Form S-8 (the “Registration Statement”) to be filed with the Securities and Exchange Commission on October 30, 2017, which Units may be issued from time to time in accordance with the terms of the BP Midstream Partners LP 2017 Long Term Incentive Plan (as amended from time to time, the “Plan”).

In reaching the opinions set forth herein, we have examined and are familiar with originals or copies, certified or otherwise identified to our satisfaction, of such documents and records of the Partnership and such statutes, regulations and other instruments as we deemed necessary or advisable for purposes of this opinion, including (i) the Registration Statement, (ii) certain resolutions adopted by the board of directors of the general partner of the Partnership, (iii) the Plan, and (iv) such other certificates, instruments, and documents as we have considered necessary for purposes of this opinion. As to any facts material to our opinion, we have made no independent investigation or verification 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 Partnership.

We have assumed (i) the legal capacity of all natural persons, (ii) the genuineness of all signatures, (iii) the authority of all persons signing all documents submitted to us on behalf of the parties to such documents, (iv) the authenticity of all documents submitted to us as originals, (v) the conformity to authentic original documents of all documents submitted to us as copies, (vi) that all information contained in all documents reviewed by us is true, correct and complete, and (vii) that the Units will be issued in accordance with the terms of the Plan.

Based on the foregoing and subject to the limitations set forth herein, and having due regard for the legal considerations we deem relevant, we are of the opinion that the Units have been duly authorized and, when the Units are issued by the Partnership in accordance with the terms of the Plan and the instruments executed pursuant to the Plan, as applicable, which govern the awards to which any Unit relates, the Units will be validly issued, fully paid (to the extent required by the Partnership’s partnership agreement) and non-assessable, except as such nonassessability may be limited by Sections 17-303, 17-607 and 17-804 of the Delaware Revised Uniform Limited Partnership Act or within the Partnership’s partnership agreement.

This opinion is limited in all respects to the Delaware Revised Uniform Limited Partnership Act. We express no opinion as to any matter other than as expressly set forth above, and no opinion on any other matter may be inferred or implied herefrom. The opinions expressed herein are rendered as of the date hereof and we expressly disclaim any obligation to update this letter or advise you of any change in any matter after the date hereof.

Vinson & Elkins LLP Attorneys at Law Austin Beijing Dallas Dubai Hong Kong Houston London Moscow New York Palo Alto Richmond Riyadh San Francisco Taipei Tokyo Washington 1001 Fannin Street, Suite 2500 Houston, TX 77002-6760 Tel +1.713.758.2222 Fax +1.713.758.2346 www.velaw.com

Page 2

This opinion letter may be filed as an exhibit to the Registration Statement. In giving this consent, we do not thereby admit that we come within the category of persons whose consent is required under Section 7 of the Act.

Very truly yours,

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

Vinson & Elkins L.L.P.