Exhibit 5.1

150 Third Avenue South, Suite 2800

Nashville, TN 37201

(615) 742-6200

January 17, 2012

Cracker Barrel Old Country Store, Inc.

305 Hartmann Drive, P.O. Box 787

Lebanon, Tennessee 37088-0787

Re: Post-Effective Amendment to Registration Statements on Form S-8

Ladies and Gentlemen:

On or about the date hereof, the Successor Registrant (defined below), as the successor registrant to the Predecessor Registrant (defined below) is filing with the Securities and Exchange Commission (the “Commission”) pursuant to Rule 414 under the Securities Act of 1933, as amended (the “Securities Act”) a Post-Effective Amendment No. 1 (the “Amendment”) to the registration statements on Form S-8, File Nos. 333-174744, 333-111364, 333-71384, 333-63442, 333-81063, 33-45482 and 33-37567 (the “Registration Statements”), originally filed by the Predecessor Registrant (defined below).

This succession occurred on December 23, 2011 as part of a planned internal recapitalization of Cracker Barrel Old Country Store, Inc., a Tennessee corporation (the “Predecessor Registrant”), through its completion of a merger (the “Merger”) with and into CBOCS, Inc., a Tennessee corporation and, prior to the Merger, a wholly-owned subsidiary of the Predecessor Registrant (the “Successor Registrant”), such that the Predecessor Registrant’s separate corporate existence ceased and the Successor Registrant continued as the surviving corporation, in accordance with the Agreement and Plan of Merger, dated October 11, 2011 by and between the Predecessor Registrant and the Successor Registrant. Upon consummation of the Merger, the Successor Registrant changed its name to “Cracker Barrel Old Country Store, Inc.” In connection with the Merger, the Successor Registrant continued the stock incentive compensation plans of the Predecessor Registrant, and assumed and adopted the Registration Statements, and as a result, shares of the Successor Registrant’s Common Stock (as defined below) are issuable pursuant thereto.

The Registration Statements, as amended by the Amendment, relate to the offering and sale by the Successor Registrant of certain shares of the Successor Registrant’s Common Stock, par value $0.01 per share (“Common Stock”), under the 2010 Omnibus Stock and Incentive Plan, 2002 Omnibus Incentive Compensation Plan, 2000 Non-Executive Stock Option Plan, 1989 Non-Employee Director’s Stock Option Plan and Amended and Restated Stock Option Plan, as continued by the Successor Registrant (the “Plans”). We have acted as counsel to the Successor Registrant in connection with the preparation and filing of the Amendment.

Cracker Barrel Old Country Store, Inc.

January 17, 2012

Page 2

In connection with this opinion, we have examined and relied upon such records, documents, certificates, and other instruments as in our judgment are necessary or appropriate in order to express the opinions hereinafter set forth. We have also assumed the legal capacity of all natural persons, the authenticity of all documents submitted to us as originals and the conformity to originals of all documents submitted to us as copies, the genuineness of the signatures of persons signing all documents in connection with which this opinion is rendered, the authority of such persons signing on behalf of the parties thereto and the due authorization, execution and delivery of all documents by the parties thereto.

Based upon and subject to the foregoing qualifications, assumptions and limitations and the further limitations set forth below, we are of the opinion that the shares of Common Stock issuable in connection with the Plans have been duly authorized and, when issued in accordance with the terms of the Plans, will be validly issued, fully paid and nonassessable.

We hereby consent to the filing of this opinion with the Commission as Exhibit 5.1 to the Amendment, and to the use of our name under the heading “Legal Opinions” in any prospectus constituting a part thereof. 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, 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 Amendment and may not be relied upon for any other purpose without our prior written consent.

Yours very truly,

/s/ Bass, Berry & Sims PLC

CIRCULAR 230 DISCLOSURE

TO ENSURE COMPLIANCE BY THIS LAW FIRM WITH REQUIREMENTS IMPOSED BY THE INTERNAL REVENUE SERVICE, WE INFORM YOU THAT THIS ADVICE WAS NOT INTENDED OR WRITTEN TO BE USED, AND CANNOT BE USED BY THE ADDRESSEE OR ANY OTHER PERSON, FOR THE PURPOSE OF (A) AVOIDING UNITED STATES FEDERAL TAX PENALTIES, OR (B) PROMOTING, MARKETING OR RECOMMENDING TO ANOTHER PARTY ANY TAX-RELATED MATTER ADDRESSED HEREIN.