Exhibit 5.1

July 25, 2012

Bloomin’ Brands, Inc.

2202 North West Shore Boulevard, Suite 500

Tampa, Florida 33607

Ladies and Gentlemen:

We have acted as counsel for Bloomin’ Brands, Inc., a Delaware corporation (the “Company”), in connection with the Registration Statement on Form S-1, File No. 333-180615 (the “Registration Statement”), filed by the Company with the Securities and Exchange Commission (the “Commission”) under the Securities Act of 1933, as amended (the “Securities Act”). The Registration Statement relates to the offer and sale of up to 24,642,855 shares of the Company’s common stock, par value $0.01 per share (the “Common Stock”), which includes up to 10,714,285 shares of Common Stock to be issued and sold by the Company (the “Primary Shares”) and up to 13,928,570 shares to be offered and sold by certain selling stockholders named in the Registration Statement (the “Selling Stockholders”) (including 3,214,285 shares subject to the underwriters’ over-allotment option described in the Registration Statement) (the “Secondary Shares” and together with the Primary Shares, the “Shares”). The terms “Primary Shares” and “Secondary Shares” shall also include any additional shares of Common Stock registered by the Company pursuant to Rule 462(b) under the Securities Act in connection with the offering contemplated by the Registration Statement. The Shares are proposed to be sold pursuant to an underwriting agreement (the “Underwriting Agreement”) to be entered into among the Company and Merrill Lynch, Pierce, Fenner & Smith Incorporated, Morgan Stanley & Co. LLC and J.P. Morgan Securities LLC, as representatives of the underwriters named therein.

We have examined such documents and such matters of fact and law as we deem necessary to render the opinions contained herein. In our examination, we have assumed, but have not independently verified, the genuineness of all signatures, the conformity to original documents of all documents submitted to us as certified, facsimile or other copies, and the

authenticity of all such documents. As to questions of fact material to this opinion, we have relied on certificates or comparable documents of public officials and of officers and representatives of the Company.

Based on the foregoing, and subject to the qualifications stated herein, we are of the opinion that:

(i) when the Company files its Second Amended and Restated Certificate of Incorporation with the Secretary of State of the State of Delaware, a form of which has been filed as an exhibit to the Registration Statement, when the price at which the Primary Shares are to be sold has been approved by or on behalf of the Board of Directors of the Company and when the Primary Shares have been issued and sold as contemplated in the Registration Statement, and upon payment and delivery in accordance with the Underwriting Agreement, the Primary Shares will be validly issued, fully paid and non-assessable; and

(ii) the Secondary Shares are validly issued, fully paid and non-assessable.

The opinions expressed herein are limited to the General Corporation Law of the State of Delaware and we express no opinion as to the effect on the matters covered by this letter of the laws of any other jurisdiction.

We hereby consent to the filing of this letter as Exhibit 5.1 to the Registration Statement and to the reference to our firm under the caption “Legal Matters” in the prospectus included therein. We further consent to the incorporation by reference of this letter and consent into any registration statement filed pursuant to Rule 462(b) with respect to the Shares. In giving such consent, we do not hereby 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.

Very truly yours,

/s/ Baker & Hostetler LLP