Exhibit 23.1

Consent of Independent Registered Public Accounting Firm

The Board of Directors

Valero Energy Corporation:

We consent to the use of our report dated September 19, 2013, with respect to the combined balance sheets of Valero Energy Partners LP Predecessor as of December 31, 2012 and 2011, and the related combined statements of income, changes in net investment, and cash flows for each of the years in the two-year period ended December 31, 2012, and our report dated September 19, 2013, with respect to the balance sheet of Valero Energy Partners LP as of August 13, 2013, included in the Registration Statement (Form S-1 No. 333-191259) and to the reference to our firm under the heading “Experts” in the related prospectus.

/s/ KPMG LLC

San Antonio, Texas

December 10, 2013