Exhibit 5.1

[Letterhead of Simpson Thacher & Bartlett LLP]

May 21, 2013

Office Depot, Inc.

6600 North Military Trail

Boca Raton, Florida 33496

Ladies and Gentlemen:

We have acted as counsel to Office Depot, Inc., a Delaware corporation (the “Company”), in connection with the Registration Statement on Form S-4 (the “Registration Statement”) filed by the Company with the Securities and Exchange Commission (the “Commission”) under the Securities Act of 1933, as amended, relating to the issuance by the Company of up to 249,494,000 shares of Common Stock, par value $0.01 per share (the “Shares”), in connection with the merger contemplated by the Agreement and Plan of Merger, dated as of February 20, 2013 (the “Merger Agreement”), by and among the Company, Dogwood Merger Sub Inc., Dogwood Merger Sub LLC, Mapleby Holdings Merger Corporation, Mapleby Merger Corporation and OfficeMax Incorporated.

We have examined the Registration Statement, the Merger Agreement and a form of the certificate representing shares of Common Stock of the Company, which has been filed with the Commission as an exhibit to the Registration Statement. We also have examined the originals, or duplicates or certified or conformed copies, of such records, agreements, documents and other instruments and have made such other investigations as we have deemed relevant and necessary in connection with the opinions hereinafter set forth. As to questions of fact material to this opinion, we have relied upon certificates or comparable documents of public officials and of officers and representatives of the Company.

In rendering the opinion set forth below, we have assumed the genuineness of all signatures, the legal capacity of natural persons, the authenticity of all documents submitted to us as originals, the conformity to original documents of all documents submitted to us as duplicates or certified or conformed copies and the authenticity of the originals of such latter documents.

Based upon the foregoing, and subject to the qualifications, assumptions and limitations stated herein, we are of the opinion that, when the Shares have been issued in accordance with the terms and conditions set forth in the Merger Agreement, the Shares will be validly issued, fully paid and nonassessable.

We do not express any opinion herein concerning any law other than the Delaware General Corporation Law (including the statutory provisions, all applicable provisions of the Delaware Constitution and reported judicial decisions interpreting the foregoing).

We hereby consent to the filing of this opinion letter as Exhibit 5 to the Registration Statement and to the use of our name under the caption “Legal Matters” in the Joint Proxy Statement/Prospectus included in the Registration Statement.

Very truly yours,

/s/ SIMPSON THACHER & BARTLETT LLP