Exhibit 5.1

Proskauer Rose LLP 2049 Century Park East, 32nd Floor Los Angeles, CA 90067-3206

May 23, 2018

Floor & Decor Holdings, Inc.

2233 Lake Park Drive

Smyrna, GA 30080

Ladies and Gentlemen:

We are acting as counsel to Floor & Decor Holdings, Inc., a Delaware corporation (the “Company”), in connection with the preparation and filing with the Securities and Exchange Commission under the Securities Act of 1933, as amended (the “Securities Act”), of a registration statement on Form S-3 (the “Registration Statement”) filed on May 23, 2018, in connection with the registration by the Company under the Securities Act of (A) the offer and sale by the Company of an indeterminate number of the following securities: (i) shares of the Company’s Class A Common Stock, par value $.001 per share (the “Common Stock”); (ii) preferred stock, par value $.001 per share (the “Preferred Stock”); (iii) debt securities (the “Debt Securities”); (iv) warrants representing rights to purchase Common Stock, Preferred Stock or Debt Securities, separately or as units comprised of any combination of the foregoing (the “Warrants”); (v) subscription rights to purchase Common Stock (the “Rights”) and (vi) units comprised of a combination of any of the foregoing securities (the “Units” and, together with the Common Stock, the Preferred Stock, the Debt Securities, the Warrants and the Rights, the “Securities” and each a “Security”) and (B) the offer and sale by certain selling stockholders to be identified in one or more prospectus supplements of an indeterminate number of shares of Common Stock. The offering of the Securities will be as set forth in the prospectus contained in the Registration Statement (the “Prospectus”), as supplemented by one or more supplements to the Prospectus.

This opinion is being furnished to you at your request to enable you to fulfill the requirements of Item 601(b)(5) of Regulation S-K, 17 C.F.R § 229.601(b)(5), in connection with the Registration Statement.

As such counsel, we have participated in the preparation of the Registration Statement and have examined originals or copies of such documents, corporate records and other instruments as we have deemed relevant, including, without limitation: (i) the restated certificate of incorporation of the Company in the form filed as Exhibit 3.1 to the Registration Statement (the “Certificate of Incorporation”); (ii) the second amended and restated bylaws of the Company in the form filed as Exhibit 3.2 to the Registration Statement; (iii) the form of indenture for the Debt Securities to be entered into between the Company and a trustee qualified to act as such under the Trust Indenture Act of 1939, as amended (the “Trust Indenture Act”) and filed as an exhibit to the Registration Statement; (iv) the resolutions of the Board of Directors of the Company (the “Board”); (v) the Registration Statement, together with the exhibits filed as a part thereof; and (vi) such corporate records of the Company, certificates of public officials, officers of the Company and other persons and such other certificates, statutes and other instruments and documents as we consider appropriate for purposes of the opinions hereafter expressed.

We have made such examination of law as we have deemed necessary to express the opinions contained herein. As to matters of fact relevant to this opinion, we have relied upon, and assumed without independent verification, the accuracy of certificates of public officials and officers of the Company. We have assumed the genuineness of all signatures, the legal capacity of natural persons, the authenticity of documents submitted to us as originals, the conformity to the original documents of all documents submitted to us as certified, facsimile, electronic or photostatic copies, and the authenticity of the originals of such copies. In making our examination of executed documents, we have assumed (a) that the parties thereto (i) are duly organized and validly existing in good standing in their respective jurisdictions of incorporation or formation, (ii) have complied with all aspects of the laws of their respective jurisdictions of incorporation or formation in connection with the issuance of the Securities and the related transactions and (iii) had the power, corporate or other, to enter into and perform all obligations thereunder and (b) the due authorization by all requisite action, corporate or other (“Company Action”), and the execution and delivery by the parties thereto of such documents and the validity and binding effect thereof on such parties.

In addition, we have assumed that (a) the issuance, sale, amount and terms of any Securities of the Company to be offered from time to time will have been duly authorized and established by proper Company Action (b) at the time of offer, issuance and sale of any Securities, the Registration Statement will have been declared effective under the Securities Act, and no stop order suspending its effectiveness will have been issued and remain in effect; (c) any Debt Securities will be issued pursuant to one or more indentures, each to be between the Company and a financial institution identified therein as trustee; (d) the indenture under which any Debt Securities are issued will be qualified under the Trust Indenture Act; (e) any Warrants will be issued under one or more warrant agreements, each to be between the Company and a financial institution identified therein as warrant agent; (f) any Rights will be issued under one or more agreements defining the Rights (a “rights agreement”), each to be between the Company and a financial institution identified therein; (g) any Units will be issued under one or more agreements defining the Units (a “unit agreement”), each to be between the Company and a financial institution identified therein; (h) if being sold by the Company, the Securities will be delivered against payment of cash or other lawful consideration therefor and in accordance with the terms of the applicable Company Action authorizing such sale and any applicable underwriting agreement or purchase agreement and as contemplated by the Registration Statement and/or the applicable prospectus supplement; (i) the laws of the State of New York will be the governing law under any indenture, warrant agreement, rights agreement or unit agreement; and (j) the Company will remain a Delaware corporation.

To the extent our opinions set forth below relate to the enforceability of the choice of New York law and choice of New York forum provisions, our opinion is rendered in reliance upon N.Y. Gen. Oblig. Law §§5-1401, 5-1402 (McKinney 2001) and N.Y. C.P.L.R. 327(b) (McKinney 2001) and is subject to the qualification that such enforceability may be limited by public policy considerations of any jurisdiction, other than the courts of the State of New York, in which enforcement of such provisions, or of a judgment upon an agreement containing such provisions, is sought. We have also assumed that the Company has complied with all aspects of applicable laws of jurisdictions other than the State of New York in connection with the transactions contemplated hereby. As to facts material to the opinions expressed herein, we have relied upon statements and representations of officers and other representatives of the Company, public officials and others.

Our opinions set forth herein are limited to (A) the laws of the State of New York that, in our experience, are applicable to securities of the type covered by the Registration Statement, (B) the General Corporation Law of the State of Delaware, and (C) to the extent that judicial or regulatory orders or decrees or consents, approvals, licenses, authorizations, validations, filings, recordings or registrations with governmental authorities are relevant, to those required under such laws (all of the foregoing being referred to as “Covered Law”). We do not express any opinion with respect to the law of any jurisdiction other than the Covered Law or as to the effect of any such non-covered law on the opinions herein stated.

The opinions set forth below are subject to the following further qualifications, assumptions and limitations:

(a) we do not express any opinion as to the enforceability of any rights to indemnification or contribution that may be violative of the public policy underlying any law, rule or regulation (including any federal or state securities law, rule or regulation); and

(b) we do not express any opinion as to any provision with respect to the enforceability of (i) any consent to, or restriction upon, governing law, jurisdiction, venue, arbitration, remedies or judicial relief, (ii) any provision that allows liquidated damages, prepayment fees, cumulative remedies, late charges, default interest, make-whole premiums or forfeitures or other economic remedies to the extent such provisions are deemed to constitute a penalty or (iii) any provision requiring the payment of attorneys’ fees, where such payment is contrary to law or public policy, or the severability, if invalid, of provisions to the foregoing effect.

Based upon the foregoing, and subject to the limitations, qualifications, exceptions and assumptions expressed herein, we are of the opinion, assuming no change in the applicable law or pertinent facts, that:

1) The Common Stock, when (i) the Board (or a duly constituted and acting committee thereof) has taken all necessary action to approve the issuance and sale of the Common Stock, the terms of the offering thereof and related matters, (ii) such shares of Common Stock have been issued and delivered in accordance with the provisions of any applicable convertible or exchangeable security, definitive purchase, underwriting or other agreement binding on the Company and the terms approved by the Board (or a duly constituted and acting committee thereof) and (iii) the Company has received payment of the cash or other lawful consideration provided to be paid for the Common Stock, which consideration shall not be less than the par value thereof, such shares of Common Stock will be legally issued, fully paid and non-assessable.

2) The Preferred Stock, when (i) the Board (or a duly constituted and acting committee thereof) has taken all necessary action to approve the designation of the relative rights, preferences and limitations of any series of Preferred Stock, (ii) a Certificate of Designations relating to such series of Preferred Stock has been properly filed with the Secretary of State of the State of Delaware, (iii) the Board (or a duly constituted and acting committee thereof) has taken all necessary action to approve the issuance and sale of such shares of Preferred Stock, the terms of the offering thereof and related matters, (iv) such shares of Preferred Stock have been issued and delivered in accordance with the provisions of any applicable convertible or exchangeable security, definitive purchase, underwriting or other agreement binding on the Company and the terms approved by the Board (or a duly constituted and acting committee thereof) and (v) the Company has received payment of the cash or other lawful consideration provided to be paid for the Preferred Stock, which consideration shall not be less than the par value thereof, such shares of Preferred Stock will be legally issued, fully paid and non-assessable.

3) The Debt Securities, upon due execution and delivery of an indenture relating thereto on behalf of the Company and the trustee named therein, and upon authentication by such trustee and due execution and delivery on behalf of the Company in accordance with the indenture and any supplemental indenture relating thereto, will constitute legal, valid and binding obligations of the Company, enforceable against the Company in accordance with the terms thereof.

4) The Warrants, upon due execution and delivery of a warrant agreement relating thereto on behalf of the Company and the warrant agent named therein and due authentication of the Warrants by such warrant agent, and upon due execution and delivery of the Warrants on behalf of the Company, will constitute legal, valid and binding obligations of the Company, enforceable against the Company in accordance with the terms thereof.

5) The Rights, upon due execution and delivery of a rights agreement relating thereto on behalf of the Company, and, if applicable, upon due execution and delivery of one or more certificates bearing such terms on behalf of the Company, global securities therefor or the entry of the issuance in the books and records of the Company, will constitute legal, valid and binding obligations of the Company, enforceable against the Company in accordance with the terms thereof.

6) The Units, upon due execution and delivery of a unit agreement relating thereto on behalf of the Company and the unit agent named therein and due authentication of the Units by such unit agent, and upon due execution and delivery of the Units on behalf of the Company, will constitute legal, valid and binding obligations of the Company, enforceable against the Company in accordance with the terms thereof.

The opinions set forth above are subject, as to enforcement, to bankruptcy, insolvency, fraudulent conveyance, fraudulent transfer, reorganization, moratorium and other similar laws relating to or affecting creditors’ rights generally and by general equitable principles (regardless of whether enforcement is sought in equity or at law), including, without limitation, principles regarding good faith and fair dealing (including the possible unavailability of specific performance or injunctive relief, concepts of materiality and reasonableness, and the discretion of the court before which a proceeding is brought).

In rendering the opinions set forth above, we have assumed that the execution and delivery by the Company of the Securities and any indenture, warrant agreement, rights agreement or unit agreement and the performance by the Company of its obligations thereunder do not and will not violate, conflict with or constitute a default under any agreement or instrument to which the Company or its properties is subject. We hereby consent to the filing of this opinion with the Commission as an exhibit to the Registration Statement.

We hereby consent to the filing of this opinion letter as Exhibit 5.1 to the Registration Statement and to the reference to our firm under the caption “Legal Matters” in the prospectus contained in the Registration Statement, and we further consent to the incorporation of this opinion by reference in any registration statement filed pursuant to Rule 462(e) under the Securities Act in connection with the offering covered by 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. This opinion is expressed as of the date hereof unless otherwise expressly stated, and we disclaim any undertaking to advise you of any subsequent changes in the facts stated or assumed herein or of any subsequent changes in applicable law.

Very truly yours,

/s/ Proskauer Rose LLP