Exhibit 5.1

Tel +1.214.220.7700 Fax +1.214.999.7816

March 18, 2022

Holly Energy Partners, L.P.

2828 N. Harwood, Suite 1300

Dallas, Texas 75201

Re: Registration Statement on Form S-3

Ladies and Gentlemen:

We have acted as counsel for Holly Energy Partners, L.P., a Delaware limited partnership (the “Partnership”), with respect to certain legal matters in connection with the preparation of a 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 under the Securities Act of 1933 (the “Securities Act”) of the offer and resale, from time to time, pursuant to Rule 415 under the Securities Act, by the unitholder named as the Selling Unitholder in the Registration Statement, of up to 21,000,000 issued and outstanding common units representing limited partner interests in the Partnership (the “Common Units”).

In rendering the opinions set forth below, we have reviewed and relied upon (i) the Registration Statement, (ii) the Certificate of Limited Partnership of the Partnership, (iii) the Second Amended and Restated Agreement of Limited Partnership of the Partnership, (iv) the First Amended and Restated Agreement of Limited Partnership of HEP Logistics Holdings, L.P., a Delaware limited partnership and the general partner of the Partnership (the “General Partner”), as amended to date, (v) the First Amended and Restated Limited Liability Company Agreement of Holly Logistic Services, L.L.C., a Delaware limited liability company and the general partner of the General Partner (the “Ultimate General Partner”), (vi) certain resolutions adopted by the Board of Directors of the Ultimate General Partner relating to the Registration Statement, and (vii) such other certificates, statutes, documents and records as we have deemed necessary and relevant for the purpose of rendering the opinions set forth below. In addition, we have reviewed such questions of law as we considered necessary or appropriate. As to matters of fact relevant to the opinions expressed below, and as to factual matters arising in connection with our review of partnership and limited liability company documents, records and other documents and writings, we have relied upon certificates and other communications from officers and employees of the Ultimate General Partner, without further investigation as to the facts set forth therein.

Vinson & Elkins LLP Attorneys at Law   Austin Dallas Dubai Houston London Los Angeles New York   Richmond Riyadh San Francisco Tokyo Washington Trammell Crow Center, 2001 Ross Avenue, Suite 3900   Dallas, TX 75201-2975   Tel +1.214.220.7700 Fax +1.214.220.7716 velaw.com

March 18, 2022 Page 2

For purposes of rendering the opinions set forth below, we have made the following assumptions:

(i) the Registration Statement, and any amendments thereto (including post-effective amendments), will have become effective and comply with all applicable laws;

(ii) each document submitted to us for review is accurate and complete, each such document that is an original is authentic, each such document that is a copy conforms to an authentic original, and all signatures on each such document are genuine;

(iii) each person signing the documents that we examined has the legal capacity and authority to do so;

(iv) each certificate from governmental officials reviewed by us is accurate, complete and authentic, and all official public records are accurate and complete; and

(v) the Common Units will be sold in compliance with applicable federal and state securities laws and in the manner stated in the Registration Statement and any applicable prospectus supplement.

Based upon and subject to the foregoing, and subject to the qualifications and limitations set forth herein, we are of the opinion that the Common Units are duly authorized, validly issued, fully paid and nonassessable (except as such nonassessability may be affected by Sections 17-303, 17-607 and 17-804 of the Delaware Revised Uniform Limited Partnership Act (“DRULPA”)).

Our opinion is qualified in the following respects:

(i) our opinion herein is limited in all respects to the federal laws of the United States of America, the Delaware Limited Liability Company Act, the DRULPA and the Constitution of the State of Delaware (including all applicable statutory provisions and reported judicial decisions interpreting those laws), and we are expressing no opinion as to the applicability or effect of the laws of any other jurisdiction, domestic or foreign;

(ii) we express no opinion as to any matter other than as set forth herein, and no opinion may be inferred or implied herefrom; and

(iii) our opinion is given as of the date hereof, and we undertake no, and hereby disclaim any, obligation to advise you of any change in any matter set forth herein.

March 18, 2022 Page 3

We hereby consent to the filing of this opinion as an exhibit to the Registration Statement and to the reference to our firm under the caption “Legal Matters” in the prospectus forming part of 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.