Exhibit 5.1

November 24, 2015

RE/MAX Holdings, Inc.

5075 South Syracuse Street

Denver, Colorado 802375

Re: Offer and Sale of Shares of Class A Common Stock of RE/MAX Holdings, Inc.

Ladies and Gentlemen:

We have acted as counsel to RE/MAX Holdings, Inc., a Delaware corporation (the “Company”), in connection with (i) the issuance of up to 5,175,000 shares  of the Company’s Class A common stock, par value $0.0001 per share (the “Common Stock”), issued by the Company to a certain holder of common units (“Units”) in RMCO, LLC (the “Operating LLC”) upon tender of Units for exchange in accordance with the terms of the Fourth Amended and Restated Limited Liability Company Agreement, dated as of October 1, 2013, of the Operating LLC (the “LLC Agreement”), and (ii) the offer and sale by the selling stockholder named in the prospectus supplement, dated November 18, 2015, to the prospectus, dated November 9, 2015, of up to 5,175,000 shares (including 675,000 shares to be sold if the underwriters exercise their over-allotment option in full) of Common Stock (the “Shares”) pursuant to a Registration Statement on Form S-3 (File No. 333-207629) (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”) on October 27, 2015 and declared effective by the Commission on November 9, 2015.

As counsel for the Company, we have examined originals or copies, certified or otherwise identified to our satisfaction, of such documents, corporate records, certificates of public officials and other instruments as we have deemed necessary for the purposes of rendering this opinion and we are familiar with the proceedings taken and proposed to be taken by the Company in connection with the authorization, issuance and sale of the Shares. In our examination, we have assumed the genuineness of all signatures, the authenticity of all documents submitted to us as originals and the conformity with the originals of all documents submitted to us as copies.

Based upon, subject to and limited by the foregoing, we are of the opinion that the Shares (including, if and when issued, the 675,000 shares to be sold if the underwriters exercise their over-allotment option in full) are validly issued, fully paid and nonassessable.

We consent to the use of this opinion as an exhibit to a Current Report on Form 8-K and the incorporation by reference of this opinion as an exhibit to the Registration Statement, and we consent to the reference of our name under the caption “Legal Matters” in the prospectus and prospectus supplement forming a part of the Registration Statement. In giving such 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.

Very truly yours,

/s/ Morrison & Foerster LLP

2