Exhibit 5.1

December 2, 2011

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 sale, from time to time, pursuant to Rule 415 under the Securities Act, by:

(i) the Partnership of (a) common units representing limited partnership interests in the Partnership (the “Common Units”), (b) preferred units representing limited partnership interests in the Partnership (the “Preferred Units”) and (c) debt securities, which may be issued in one or more series, consisting of debentures, notes, bonds or other evidences of indebtedness (the “Debt Securities”), and which may be co-issued by Holly Energy Finance Corp., a Delaware corporation (“Finance Corp.”), at an aggregate initial offering price not to exceed $2,000,000,000;

(ii) any subsidiary of the Partnership listed on Schedule I hereto (collectively, the “Subsidiary Guarantors”) or any combination of the Subsidiary Guarantors of guarantees of the Debt Securities (the “Guarantees” and, together with the Common Units, the Preferred Units and the Debt Securities, the “Primary Securities”); and

(iii) the unitholders named as the Selling Unitholders in the Registration Statement, of up to 11,097,615 common units representing limited partnership interests in the Partnership (the “Secondary Units” and, together with the Primary Securities, the “Securities”).

We have also participated in the preparation of the prospectus contained in the Registration Statement (the “Prospectus”) to which this opinion is an exhibit. The Securities will be offered in amounts, at prices and on terms to be determined in light of market conditions and other factors at the time of sale and, if necessary, will be set forth in supplements (each, a “Prospectus Supplement”) to the Prospectus.

Vinson & Elkins LLP Attorneys at Law Abu Dhabi    Austin    Beijing    Dallas    Dubai    Hong Kong    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

December 2, 2011    Page 2

In rendering the opinions set forth below, we have reviewed and relied upon (i) the Registration Statement, (ii) the Prospectus, (iii) the form of Senior Indenture (the “Senior Indenture”) filed as an exhibit to the Registration Statement, (iv) the form of Subordinated Indenture (the “Subordinated Indenture” and, together with the Senior Indenture, the “Indentures”) filed as an exhibit to the Registration Statement, (v) the Certificate of Limited Partnership of the Partnership, (vi) the First Amended and Restated Agreement of Limited Partnership of the Partnership, as amended to date, (vii) 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”), (viii) 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”), as amended to date, (ix) the constituent documents and agreements of Finance Corp. and the Subsidiary Guarantors, (x) certain resolutions adopted by the Board of Directors of the Ultimate General Partner relating to the Registration Statement, (xi) certain resolutions adopted by the Board of Directors of Finance Corp. relating to the Registration Statement and (xii) 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, corporate and limited liability company documents, records and other documents and writings, we have relied upon certificates and other communications of officers and employees of the Ultimate General Partner and Finance Corp., without further investigation as to the facts set forth therein.

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;

(ii) a Prospectus Supplement (where applicable) will have been prepared and filed with the Commission describing the Securities offered thereby;

(iii) 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;

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

December 2, 2011    Page 3

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

(vi) all Securities will be issued and sold in compliance with applicable federal and state securities laws and in the manner stated in the Registration Statement and the Prospectus Supplement, if any;

(vii) the Indentures relating to the Debt Securities, together with any supplemental indentures relating to a series of Debt Securities to be issued under either of the Indentures, will each be duly authorized and validly executed and delivered by the parties thereto;

(viii) each Subsidiary Guarantor is duly organized, validly existing and in good standing under the laws of its jurisdiction;

(ix) at the time of the issuance of any Debt Securities, the Partnership will validly exist and be duly qualified and in good standing under the laws of its jurisdiction of formation and will have the necessary organizational power and authority to issue such Debt Securities;

(x) at the time of the issuance of any Debt Securities co-issued by Finance Corp., Finance Corp. will validly exist and be duly qualified and in good standing under the laws of its jurisdiction of formation and will have the necessary organizational power and authority to issue such Debt Securities;

(xi) at the time of the issuance of any Debt Securities, the Subsidiary Guarantors will validly exist and be duly qualified and in good standing under the laws of its jurisdiction of formation and will have the necessary organizational power and authority to issue the Guarantees;

(xii) at the time of any offering or sale of any Common Units or Preferred Units, the Partnership will have authorized or created and made available for issuance the number of Common Units and/or Preferred Units set forth in such offering or sale;

(xiii) a definitive purchase, underwriting or similar agreement with respect to any Securities offered will have been duly authorized and validly executed and delivered by the Partnership and the other parties thereto; and

(xiv) any Common Units or Preferred Units issuable upon conversion, exchange or exercise of any Primary Securities being offered will have been duly authorized, issued and, if appropriate, reserved for issuance upon such conversion, exchange or exercise.

December 2, 2011    Page 4

Based upon and subject to the foregoing, and subject to the qualifications and limitations set forth herein, we are of the opinion that:

(1) the Common Units will be duly authorized, validly issued, fully paid and non-assessable when (a) the Partnership has taken all necessary action to approve the issuance of such Common Units, the terms of the offering thereof and related matters and (b) the Common Units have been issued and delivered either (i) in accordance with the terms of the applicable definitive purchase, underwriting or similar agreement approved by the Partnership upon payment of the consideration thereof provided for therein or (ii) upon conversion, exchange or exercise of any other Primary Securities in accordance with the terms of the Primary Security and the instrument governing the Primary Security providing for the conversion, exchange or exercise;

(2) the Preferred Units will be duly authorized, validly issued, fully paid and non-assessable when (a) the Partnership has taken all necessary action to duly authorize and approve the issuance of such Preferred Units, the terms of the offering thereof and related matters and (b) the Preferred Units have been issued and delivered either (i) in accordance with the terms of the applicable definitive purchase, underwriting or similar agreement approved by the Partnership upon payment of the consideration thereof provided for therein or (ii) upon conversion, exchange or exercise of any other Primary Securities in accordance with the terms of the Primary Security and the instrument governing the Primary Security providing for the conversion, exchange or exercise;

(3) the Debt Securities and, if applicable, the Guarantees, will be duly authorized and validly issued and will constitute valid and legally binding obligations of the Partnership, Finance Corp. and the Subsidiary Guarantors, as applicable, enforceable against the Partnership, Finance Corp. and the Subsidiary Guarantors, as applicable, in accordance with their terms, except as such enforcement is subject to any applicable bankruptcy, insolvency (including, without limitation, all laws relating to fraudulent transfers), reorganization, moratorium and similar laws relating to or affecting creditors’ rights generally and to general equitable principles (regardless of whether enforcement is sought in a proceeding in equity or at law) when (a) the applicable Indenture has been duly qualified under the Trust Indenture Act of 1939, as amended, (b) the Partnership, Finance Corp. and the Subsidiary Guarantors, as applicable, have taken all necessary action to approve the issuance and terms of the Debt Securities and, if applicable, the Guarantees, the terms of the offering thereof and related matters, (c) the terms of the Debt Securities and, if applicable, the Guarantees, and their issuance and sale have been duly established in conformity with the applicable Indenture so as not to violate

December 2, 2011    Page 5

any applicable law or result in a default under or breach of any agreement or instrument binding upon the Partnership, Finance Corp. and the Subsidiary Guarantors, as applicable, and so as to comply with any requirements or restrictions imposed by any court or governmental body having jurisdiction over the Partnership, Finance Corp. and the Subsidiary Guarantors, as applicable, and (d) the Debt Securities (which may include the related Guarantees) have been duly executed, authenticated, issued and delivered in accordance with the applicable Indenture and the applicable definitive purchase, underwriting or similar agreement approved by the Partnership, Finance Corp. and the Subsidiary Guarantors, as applicable, upon payment of the consideration for the Debt Securities as provided for therein; and

(4) the Secondary Units have been duly authorized and validly issued and are fully paid and non-assessable.

Our opinion is qualified in the following respects:

(i) we express no opinions concerning (a) the validity or enforceability of any provisions contained in the Indentures that purport to waive, or not give effect to, rights to notices, defenses, subrogation or other rights or benefits that cannot be effectively waived under applicable law or (b) the enforceability of indemnification provisions to the extent they purport to relate to liabilities resulting from or based upon negligence or any violation of federal or state securities or blue sky laws;

(ii) our opinion expressed in paragraph 4 above, insofar as it relates to the Secondary Units being fully paid, is based solely on an officer’s certificate of the Partnership, executed and delivered to us by an officer of the Ultimate General Partner, confirming the Partnership’s receipt of the consideration called for by the applicable resolutions authorizing the issuance of the Secondary Units;

(iii) our opinions herein are limited in all respects to the federal laws of the United States of America, the General Corporation Law of the State of Delaware, the Delaware Limited Liability Company Act, the Delaware Revised Uniform Limited Partnership Act, the Constitution of the State of Delaware (including all applicable statutory provisions and reported judicial decisions interpreting those laws) and the laws of the State of New York, and we are expressing no opinion as to the applicability or effect of the laws of any other jurisdiction, domestic or foreign;

(iv) we express no opinion with respect to the validity or enforceability of provisions that limit the obligation of a guarantor based on the potential unenforceability, invalidity or voidability of a guarantee under any applicable

December 2, 2011    Page 6

law, including, without limitation, any state or federal fraudulent transfer or fraudulent conveyance laws;

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

(vi) 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.

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.

VINSON & ELKINS L.L.P.

Schedule I

HEP Logistics GP, L.L.C.

Holly Energy Partners — Operating, L.P.

HEP Pipeline GP, L.L.C.

HEP Refining GP, L.L.C.

HEP Mountain Home, L.L.C.

HEP Pipeline, L.L.C.

HEP Refining, L.L.C.

HEP Woods Cross, L.L.C.

HEP Navajo Southern, L.P.

HEP Pipeline Assets, Limited Partnership

HEP Refining Assets, L.P.

HEP Fin-Tex/Trust-River, L.P.

HEP SLC, LLC

HEP Tulsa LLC

Holly Energy Storage — Lovington LLC

Holly Energy Storage — Tulsa LLC

Lovington-Artesia L.L.C.

Roadrunner Pipeline, LLC

Cheyenne Logistics LLC

El Dorado Logistics LLC

Vinson & Elkins LLP Attorneys at Law Abu Dhabi    Austin    Beijing    Dallas    Dubai    Hong Kong    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