Exhibit 5.1

Fulbright Tower • 1301 McKinney, Suite 5100 • Houston, Texas 77010-3095

Telephone: 713 651 5151 • Facsimile: 713 651 5246

December 1, 2011

Holly Energy Partners, L.P.

2828 N. Harwood, Suite 1300

Dallas, Texas 75201

Ladies and Gentlemen:

We have acted as counsel for Holly Energy Partners, L.P., a Delaware limited partnership (the “Partnership”), in connection with the proposed offering and sale by the Partnership of an aggregate of 1,475,000 common units representing limited partner interests of the Partnership (the “Firm Units”), and, at the election of the Underwriters (defined below), up to 221,250 additional common units of limited partner interests of the Partnership (the “Optional Units”) (the Firm Units and the Optional Units that the Underwriters elect to purchase being collectively called the “Common Units”) pursuant to an underwriting agreement dated December 1, 2011 (the “Underwriting Agreement”), between the Partnership, and Citigroup Global Markets Inc., Merrill Lynch, Pierce, Fenner & Smith Incorporated, and Wells Fargo Securities, LLC, as representatives of the several underwriters named therein (the “Underwriters”). Capitalized terms used in this opinion and not otherwise defined have the meanings assigned to such term in the Underwriting Agreement.

The Common Units are being offered and sold pursuant to a prospectus supplement, dated December 1, 2011, (the “Prospectus Supplement”) filed with the Securities and Exchange Commission (the “Commission”) pursuant to Rule 424(b) on December 1, 2011, to a base prospectus dated December 4, 2008 (such prospectus, as amended and supplemented by the Prospectus Supplement, the “Prospectus”), included in a Registration Statement on Form S-3 (Registration No. 333-155537), filed with the Commission pursuant to the Securities Act of 1933, as amended (the “Securities Act”), and declared effective by the Commission on December 4, 2008 (the “Registration Statement”).

In rendering the opinions set forth below, we have reviewed and relied upon originals or copies, certified or otherwise identified to our satisfaction, of (i) the certificate of limited partnership of the Partnership and the Partnership’s First Amended and Restated Agreement of Limited Partnership dated as of July 13, 2004, as amended by the Amendment No. 1 to the First Amended and Restated Agreement of Limited

AUSTIN • BEIJING • DALLAS • DENVER • DUBAI • HONG KONG • HOUSTON • LONDON • LOS ANGELES • MINNEAPOLIS

MUNICH • NEW YORK • PITTSBURGH-SOUTHPOINTE • RIYADH • SAN ANTONIO • ST. LOUIS • WASHINGTON DC

www.fulbright.com

December 1, 2011

Page 2

Partnership dated as of February 28, 2005, the Amendment No. 2 to the First Amended and Restated Agreement of Limited Partnership dated as of July 6, 2005, and the Amendment No. 3 to the First Amended and Restated Agreement of Limited Partnership dated as of April 11, 2008; (ii) certain resolutions adopted by the Board of Directors of Holly Logistic Services, L.L.C. relating to the registration of the Common Units and related matters and to the proposed offering; (iii) certain resolutions adopted by the Pricing Committee of the Board of Directors of Holly Logistic Services, L.L.C.; (iv) the Registration Statement; (v) the Prospectus; (vi) the Prospectus Supplement; (vii) the Underwriting Agreement; and (viii) such other certificates, instruments and documents as we considered appropriate for purposes of the opinion hereafter expressed. In addition, we reviewed such questions of law as we considered appropriate.

As to any facts material to the opinion contained herein, we have made no independent investigation 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.

In connection with this opinion, we have assumed without independent verification that (i) all documents submitted to us as originals are authentic, all documents submitted conform to the originals of those documents and that all documents submitted to us as drafts of documents to be executed will conform to the documents when executed; (ii) signatures on all documents examined by us are genuine; (iii) each natural person signing any document reviewed by us had the legal capacity or competence to do so; (iv) each person or entity signing in a representative capacity any document reviewed by us had authority to sign in such capacity; (v) parties other than the Partnership that have executed any document had the corporate or other power to enter into, and perform all obligations under, any such document; and (vi) all Common Units will be issued and sold in the manner stated in the Prospectus Supplement, the Prospectus and the Underwriting Agreement.

Based on the foregoing, and subject to the assumptions, limitations, and qualifications set forth herein, we are of the opinion that the Common Units, when issued and delivered to and paid for by the Underwriters in accordance with the terms of the Underwriting Agreement, will be validly issued, fully paid (to the extent required by the Partnership Agreement), and non-assessable, except as such non-assessability may be affected by Sections 17-607 and 17-804 of the Delaware Revised Uniform Limited Partnership Act and as described in the Prospectus Supplement and the Prospectus.

The opinions expressed herein are limited exclusively to the Delaware Revised Uniform Limited Partnership Act, and we are expressing no opinion as to the effect of the laws of any other jurisdiction.

We hereby consent to the filing of this opinion of counsel as Exhibit 5.1 to the Current Report on Form 8-K of the Partnership dated on or about the date hereof, to the incorporation by reference of this opinion of counsel into the Registration Statement and to the reference to our Firm under the heading “Legal Matters” in the Prospectus

December 1, 2011

Page 3

Supplement and the Prospectus. In 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.