EXHIBIT 5.1

September 6, 2007

Magellan Midstream Holdings, L.P.

One Williams Center

P.O. Box 22186

Tulsa, Oklahoma 74121-2186

Re: Sale of 8,500,000 Common Units

Ladies and Gentlemen:

We have acted as counsel for Magellan Midstream Holdings, L.P., a Delaware limited partnership (the “Partnership”), and for Magellan Midstream Holdings, GP, LLC, a Delaware limited liability company (the “General Partner”), and for MGG Midstream Holdings, L.P., a Delaware limited partnership (the “Selling Unitholder”), in connection with the proposed offering and sale by the Selling Unitholder of 8,500,000 common units representing limited partner interests in the Partnership (the “Units”), pursuant to that certain Underwriting Agreement dated September 5, 2007 (the “Underwriting Agreement”) by and among the General Partner, the Partnership, the Selling Unitholder, and Lehman Brothers Inc. and Morgan Stanley & Co. Incorporated (collectively, the “Underwriters”).

We have also participated in the preparation of the Prospectus Supplement dated September 5, 2007 (the “Prospectus Supplement”), and the accompanying Prospectus dated May 1, 2007 (the “Base Prospectus,” and together with the Prospectus Supplement, the “Prospectus”) contained in the Partnership’s Registration Statement on Form S-3 (File No. 333-141228) with respect to the Units being sold by the Selling Unitholder (the “Registration Statement”), as filed by the Partnership with the Securities and Exchange Commission (the “Commission”) pursuant to Rule 424(b) promulgated under the Securities Act of 1933, as amended (the “Securities Act”).

We have examined the Registration Statement, the Prospectus, the Underwriting Agreement, the Fourth Amended and Restated Agreement of Limited Partnership of the Partnership (the “Partnership Agreement”), the Certificate of Limited Partnership of the Partnership (the “Certificate”) filed with the Secretary of State of Delaware pursuant to the Delaware Revised Uniform Limited Partnership Act in connection with the formation of the Partnership, and such other documents as we have deemed necessary or appropriate for purposes of this opinion. In addition, we have reviewed certain certificates of officers of the general partner of the Partnership and of public officials, and we have relied on such certificates with respect to certain factual matters that we have not independently established.

Vinson & Elkins LLP Attorneys at Law Austin Beijing Dallas Dubai Houston London Moscow New York Shanghai Tokyo Washington First City Tower, 1001 Fannin Street, Suite 2300, Houston, TX 77002-6760 Tel 713.758.2222 Fax 713.758.2346 www.velaw.com

EXHIBIT 5.1, Page 2

Based on and subject to the foregoing and on such legal considerations as we deem relevant, we are of the opinion that the Units, when delivered on behalf of the Selling Unitholder against payment therefore in accordance with the terms of the Underwriting Agreement, will have been duly authorized, validly issued, fully paid (to the extent required by the Partnership Agreement) and nonassessable (except as such nonassessability may be affected by Sections 17-303 and 17-607 of the Act and otherwise by matters described in the Prospectus).

The opinion expressed herein are qualified in the following respects:

(1) We have assumed, without independent verification, that the certificates for the Units will conform to the specimens thereof examined by us and will have been duly countersigned by a transfer agent and duly registered by a registrar of the Units.

(2) We have assumed that (i) 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 and (ii) each certificate from governmental officials reviewed by us is accurate, complete and authentic, and all official public records are accurate and complete.

(3) This opinion is limited in all respects to federal laws, the Delaware Revised Uniform Limited Partnership Act and the Constitution of the State of Delaware, as interpreted by the courts of the State of Delaware and of the United States.

We hereby consent to the statements with respect to us under the heading “Legal Matters” in the Prospectus Supplement and to the filing of this opinion as an Exhibit to the Partnership’s Current Report on Form 8-K filed on or about the date hereof. In giving this consent, we do not admit that we are within the category of persons whose consent is required under the provisions of the Securities Act, or the rules and regulations of the Commission issued thereunder.

Very truly yours,

/s/ Vinson & Elkins L.L.P.