Exhibit 5.1

Paul, Weiss, Rifkind, Wharton & Garrison LLP

1285 Avenue of the Americas

New York, New York 10019-6064

November 1, 2013

Houghton Mifflin Harcourt Company

222 Berkeley Street

Boston, Massachusetts 02116

Registration Statement on Form S-1

(Registration No. 333-190356)

Ladies and Gentlemen:

We have acted as special counsel to Houghton Mifflin Harcourt Company (f/k/a HMH Holdings (Delaware), Inc.), a Delaware corporation (the “Company”), in connection with the Registration Statement on Form S-1, as amended (the “Registration Statement”), of the Company, filed with the Securities and Exchange Commission pursuant to the Securities Act of 1933, as amended (the “Act”), and the rules and regulations thereunder (the “Rules”). You have asked us to furnish our opinion as to the legality of the securities being registered under the Registration Statement. The Registration Statement relates to the registration under the Act of up to 20,987,500 shares (the “Shares”) of the Company’s common stock, par value $0.01 per share (the “Common Stock”), that may be offered by certain stockholders of the Company (including shares that may be sold by certain stockholders of the Company upon exercise of the underwriters’ over-allotment option).

2

In connection with the furnishing of this opinion, we have examined originals, or copies certified or otherwise identified to our satisfaction, of the following documents (collectively, the “Documents”):

1. the Registration Statement;

2. the form of the Underwriting Agreement (the “Underwriting Agreement”), included as Exhibit 1.1 to the Registration Statement;

3. the form of the Amended and Restated By-Laws of the Company, included as Exhibit 3.3 to the Registration Statement;

4. the Prepackaged Joint Plan of Reorganization of the Debtors under Chapter 11 of the Bankruptcy Code, dated May 11, 2012; and

5. Findings of Fact, Conclusions of Law, and Order (i) Approving the Debtors’ (a) Disclosure Statement Pursuant to Sections 1125 and 1126(b) of the Bankruptcy Code, (b) Solicitation of Votes and Voting Procedures, and (c) Forms of Ballots; (ii) Confirming the Prepackaged Joint Plan of Reorganization of the Debtors under Chapter 11 of the Bankruptcy Code; and (iii) Authorizing the Conversion of the DIP Credit Facility into the Exit Facility, dated June 21, 2012.

In addition, we have examined (i) such corporate records of the Company as we have considered appropriate, including copies of the Amended and Restated Certificate of Incorporation of the Company, as amended by the Certificate of Amendment to the Amended and Restated Certificate of Incorporation, and by-laws, as amended, of the Company, certified by the Company as in effect on the date of this letter, and copies of certain resolutions of the board of directors of the Company and written consents of certain stockholders, certified by the Company, and (ii) such other certificates,

3

agreements and documents as we deemed relevant and necessary as a basis for the opinions expressed below. We have also relied upon the representations and warranties of the Company made in the Documents as to factual matters and upon certificates of public officials and the officers of the Company.

In our examination of the documents referred to above, we have assumed, without independent investigation, the genuineness of all signatures, the legal capacity of all individuals who have executed any of the documents reviewed by us, the authenticity of all documents submitted to us as originals, the conformity to the originals of all documents submitted to us as certified, photostatic, reproduced or conformed copies of valid existing agreements or other documents, the authenticity of all the latter documents and that the statements regarding matters of fact in the certificates, records, agreements, instruments and documents that we have examined are accurate and complete.

Based upon the above, and subject to the stated assumptions, exceptions and qualifications, we are of the opinion that the Shares have been duly authorized by all necessary corporate action on the part of the Company and are validly issued, fully paid and non-assessable.

The opinion expressed above is limited to the General Corporation Law of the State of Delaware and the federal laws of the United States of America. Our opinion is rendered only with respect to the laws, and the rules, regulations and orders under those laws, that are currently in effect.

4

We hereby consent to use of this opinion as an exhibit to the Registration Statement and to the use of our name under the heading “Legal Matters” contained in the prospectus included in the Registration Statement. In giving this consent, we do not thereby admit that we come within the category of persons whose consent is required by the Act or the Rules.

Very truly yours,

/s/ Paul, Weiss, Rifkind, Wharton & Garrison LLP

PAUL, WEISS, RIFKIND, WHARTON & GARRISON LLP