Exhibit 5.1

June 2, 2006

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

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 registration by the Partnership under the Securities Act of 1933, as amended (the “Securities Act”) of the offer and sale of an aggregate of up to 350,000 common units representing limited partner interests in the Partnership (“Common Units”), pursuant to the Partnership’s Long-Term Incentive Plan (the “Plan”).

     In connection herewith, we have examined or are familiar with the Plan, the Partnership’s Certificate of Limited Partnership as in effect on the date hereof, the First Amended and Restated Agreement of Limited Partnership as amended and in effect on the date hereof, the proceedings with respect to the approval of the Plan, and the Registration Statement on Form S-8 filed in connection with the registration of the Common Units (the “Registration Statement”), and such other certificates, instruments, and documents as we have considered necessary for purposes of this opinion letter.

     Based upon the foregoing and subject to the limitations set forth herein, we are of the opinion that the Common Units have been duly authorized and, when the Common Units are issued in accordance with the terms of the Plan and the instruments executed pursuant to the Plan, which govern the awards to which the Common Units relate, will be validly issued and fully paid and non-assessable.

     The foregoing opinion is limited to the laws of the United States of America, the State of Texas, and to the Delaware Revised Uniform Limited Partnership Act, as interpreted by federal courts and the courts of the State of Delaware.

     We hereby consent to the filing of this opinion as an exhibit to the Registration Statement. In giving this consent, we do not admit that we are within the category of persons whose consent is required under Section 7 of the Securities Act and the rules and regulations thereunder.

Very truly yours,

David C. D’Alessandro
Vinson & Elkins L.L.P.

Vinson & Elkins LLP Attorneys at Law  Austin  Beijing  Dallas Dubai
Houston  London  Moscow  New  York  Shanghai  Tokyo  Washington Trammell Crow Center, 2001 Ross Avenue, Suite 3700
Dallas, TX 75201-2975   Tel 214.220.7700  Fax 214.220.7716
www.velaw.com