Exhibit 5.1

Fulbright & Jaworski l.l.p.
A Registered Limited Liability Partnership
2200 Ross Avenue, Suite 2800
Dallas, Texas 75201-2784
www.fulbright.com

December 1, 2009

Holly Energy Partners, L.P.
100 Crescent Court, Suite 1600
Dallas, Texas 75201

Re:   Holly Energy Partners, L.P. — Registration Statement on Form S-3

Ladies and Gentlemen:

     We are acting as counsel for Holly Energy Partners, L.P., a Delaware limited partnership (the “Partnership”), in connection with the proposed registration by the Company of 1,373,609 common units representing limited partner interests in the Partnership (the “Common Units”), pursuant to a Registration Statement on Form S-3, filed with the Securities and Exchange Commission (the “Commission”), under the Securities Act of 1933, as amended (the “Securities Act”, and such Registration Statement, as amended or supplemented, is hereafter referred to as the “Registration Statement”). The Common Units to be registered pursuant to the Registration Statement may be sold from time to time by the selling unitholder identified in the Registration Statement (the “Units”). The Units are issuable pursuant to an asset sale and purchase agreement dated October 19, 2009, by and between HEP Tulsa LLC, a wholly-owned subsidiary of the Partnership, Holly Refining & Marketing-Tulsa LLC, and Sinclair Tulsa Refining Company (the “Purchase Agreement”).

     In rendering the opinion 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 and the First Amended and Restated Agreement of Limited Partnership, as amended, of the Partnership; (ii) certain resolutions adopted by the Board of Directors of Holly Logistic Services, LLC relating to the registration of the Common Units and related matters and to the proposed offering; (iii) the Registration Statement; (iv) the Purchase Agreement; and (v) 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

Austin • Beijing • Dallas • Denver • Dubai • Hong Kong • Houston • London • Los Angeles • Minneapolis
Munich • New York • Riyadh • San Antonio • St. Louis • Washington DC

Holly Energy Partners, L.P.
December 1, 2009
Page 2

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 Registration Statement and the Purchase Agreement.

     Based on the foregoing, and subject to the assumptions, limitations, and qualifications set forth herein, we are of the opinion that the Units will be, when issued to the selling stockholders pursuant to the terms of the Purchase Agreement, duly authorized and 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 Registration Statement.

     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 Registration Statement 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 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.

Very truly yours,

/s/ Fulbright & Jaworski L.L.P.

FULBRIGHT & JAWORSKI L.L.P.