Exhibit 5.1

21 Platform Way South, Suite 3500

Nashville, TN 37203

(615) 742-6200

November 24, 2025

Cracker Barrel Old Country Store, Inc.
305 Hartmann Drive, P.O Box 787
Lebanon, Tennessee

RE: Registration Statement on Form S-8

Ladies and Gentlemen:

We have acted as counsel to Cracker Barrel Old Country Store, Inc., a Tennessee corporation (the “Company”), in connection with the preparation and filing of a Registration Statement on Form S-8 (the “Registration Statement”) under the Securities Act of 1933, as amended, which the Company is filing with the Securities and Exchange Commission (the “Commission”) related to the offering of an additional 1,325,000 shares of the Company’s common stock, par value $0.01 per share (the “Shares”), pursuant to the Cracker Barrel Old Country Store, Inc. 2020 Omnibus Incentive Plan, as amended, as approved by the board of directors of the Company on September 2, 2025 and by the  Company’s stockholders at the Company’s annual meeting held on November 20, 2025 (the “Amended 2020 Plan”).

In connection with this opinion, we have examined and relied upon such records, documents, certificates, and other instruments as we have deemed necessary or appropriate in order to express the opinions hereinafter set forth. We have also assumed the legal capacity of all natural persons, the genuineness of all signatures, the authenticity of all documents submitted to us as originals, the conformity to original documents of all documents submitted to us as copies, the authenticity of the originals of such latter documents, the legal competence of all signatories to such documents, and, except to the extent we express an opinion as to due authorization in the next paragraph of this letter, the due authorization, execution and delivery of all documents by the parties thereto. As to various questions of fact relevant to the opinion expressed herein, we have relied upon, and assume the accuracy of, certificates and oral or written statements and other information of or from public officials and officers and representatives of the Company.

Based upon and subject to the qualifications, assumptions and limitations set forth herein, we are of the opinion that the Shares issuable in connection with the Amended 2020 Plan have been duly authorized and, when issued in accordance with the terms of the Amended 2020 Plan and the relevant award agreements, will be legally issued, fully paid and non-assessable.

The opinions expressed above are limited to the Tennessee Business Corporation Act (which includes applicable provisions of the Tennessee State Constitution and reported judicial decisions interpreting the Tennessee Business Corporation Act and the Tennessee State Constitution).

Cracker Barrel Old Country Store, Inc.

November 24, 2025

We hereby consent to the filing of this opinion with the Commission as Exhibit 5.1 to the Registration Statement. In giving this consent, we do not thereby admit that we are in the category of persons whose consent is required under Section 7 of the Securities Act of 1933, as amended, or the rules and regulations of the Commission.

This opinion is limited to the specific issues addressed herein, and no opinion may be inferred or implied beyond that expressly stated herein.

This opinion is furnished to you in connection with the filing of the Registration Statement. Our opinion is rendered as of the date hereof and we assume no obligation to advise you of changes in law or fact (or the effect thereof on the opinions expressed herein) that hereafter may come to our attention.

Very truly yours,

/s/ Bass, Berry & Sims PLC