Exhibit 5.1

[BAKER BOTTS L.L.P. LETTERHEAD]

April 7, 2006

Liberty Media Holding Corporation
12300 Liberty Boulevard
Englewood, CO 80112

Ladies and Gentlemen:

        As counsel for Liberty Media Holding Corporation, a Delaware corporation (the "Company"), we have examined and are familiar with the Registration Statement on Form S-4 (File No. 333-132452) as amended by Amendment Number 2 thereto (the "Registration Statement"), filed by the Company on the date hereof with the Securities and Exchange Commission for the purpose of registering under the Securities Act of 1933, as amended (the "Securities Act"), 683,775,621 shares (the "Series A Liberty Interactive Shares") of the Company's Series A Liberty Interactive common stock, par value $.01 per share (the "Series A Liberty Interactive Common Stock"), 37,757,020 shares (the "Series B Liberty Interactive Shares") of the Company's Series B Liberty Interactive common stock, par value $.01 per share (the "Series B Liberty Interactive Common Stock"), 136,755,125 shares (the "Series A Liberty Capital Shares") of the Company's Series A Liberty Capital common stock, par value $.01 per share (the "Series A Liberty Capital Common Stock"), and 7,551,404 shares (the "Series B Liberty Capital Shares" and together with the Series A Liberty Interactive Shares, the Series B Liberty Interactive Shares and the Series A Liberty Capital Group Shares, the "Shares") of the Company's Series B Liberty Interactive common stock, par value $.01 per share (the "Series B Liberty Capital Common Stock" and together with the Series A Liberty Interactive Common Stock, the Series B Liberty Interactive Common Stock and the Series A Liberty Capital Common Stock, the "Common Stock"), to be issued by the Company in a merger transaction (the "Merger") in conversion of and exchange for outstanding shares of common stock of Liberty Media Corporation, a Delaware corporation ("LMC"). As of the date of this opinion, the Company is a wholly owned subsidiary of LMC. At the effective time of the Merger, a wholly owned transitory merger subsidiary of the Company will merge with and into LMC, and each outstanding share of LMC's Series A common stock, par value $.01 per share, will be converted into and exchanged for 0.25 of a share of Series A Liberty Interactive Common Stock and 0.05 of a share of Series A Liberty Capital Common Stock, and each share of LMC's Series B common stock, par value $.01 per share, will be converted into and exchanged for 0.25 of a share of Series B Liberty Interactive Common Stock and 0.05 of a share of Series B Liberty Capital Common Stock. Any fractional share interests will be settled in cash. The terms of the Merger and the Common Stock are described in the proxy statement/prospectus which forms a part of the Registration Statement to which this opinion is an exhibit.

        In connection with rendering our opinion, we have examined, among other things, originals, certified copies or copies otherwise identified to us as being copies of originals, of (i) the form of Restated Certificate of Incorporation and Bylaws of the Company to be in effect at the effective time of the Merger; (ii) the Amended and Restated Certificate of Incorporation and Bylaws of LMC as in effect on the date hereof; (iii) the Agreement and Plan of Merger (the "Merger Agreement"), dated as of April 6, 2006, among the Company, its merger subsidiary and LMC; (iv) the form of Certificate of Merger to be filed with the Secretary of State of the State of Delaware following the receipt of the requisite stockholder approvals; (v) the form of stock certificate representing the Series A Liberty Interactive Common Stock included as Exhibit 4.1 to the Registration Statement, the form of stock certificate representing the Series B Liberty Interactive Common Stock included as Exhibit 4.2 to the Registration Statement, the form of stock certificate representing the Series A Liberty Capital Group Common Stock included as Exhibit 4.3 to the Registration Statement and the form of stock certificate representing the Series B Liberty Capital Common Stock included as Exhibit 4.4 to the Registration Statement; (vi) records of proceedings of the boards of directors of the Company, its merger subsidiary

and LMC; and (vii) such other documents, records and certificates of public officials as we deemed necessary or appropriate for the purpose of rendering this opinion. In rendering this opinion, we have relied, to the extent we deem such reliance appropriate, on certificates of officers of the Company and LMC as to factual matters regarding the Company and LMC that were not readily ascertainable by us. We have assumed the authenticity of all documents submitted to us as originals and the conformity to authentic original documents of all documents submitted to us as copies.

        On the basis of such examination and review, we advise you that, in our opinion, upon the issuance and delivery of the Shares in accordance with the terms of the Merger Agreement, the Shares will be duly authorized, validly issued and non-assessable.

        This opinion is limited to the corporate laws of the state of Delaware, and the laws of the United States of America. We hereby consent to the filing of this opinion as Exhibit 5.1 to the Registration Statement and to the reference to us under the heading "Additional Information—Legal Matters" in the Registration Statement. In giving the foregoing consent, we do not admit that we are in the category of persons whose consent is required under Section 7 of the Securities Act or the rules and regulations of the Securities and Exchange Commission promulgated thereunder.

QuickLinks

Exhibit 5.1