Exhibit 5.1

December 18, 2023

Heritage Insurance Holdings, Inc.

1401 N. Westshore Blvd

Tampa, Florida 33607

Re: Heritage Insurance Holdings, Inc. Registration Statement on Form S-3 (File No: 333-254091)

Ladies and Gentlemen:

We have acted as counsel to Heritage Insurance Holdings, Inc., a Delaware corporation (the “Company”), in connection with the Company’s registration of 3,703,703 shares of the Company’s common stock, par value $0.0001 per share (the “Shares”), covered by the above-referenced registration statement (including the prospectus contained therein, the “Registration Statement”), filed by the Company with the U.S. Securities and Exchange Commission (the “Commission”) under the Securities Act of 1933, as amended (the “Securities Act”), together with the Prospectus Supplement dated December 18, 2023 (the “Prospectus Supplement”), filed with the Commission on December 18, 2023 pursuant to Rule 424(b)(5) under the Securities Act, relating to the primary offering of the Shares by the Company.

In connection with our representation of the Company and the preparation of this opinion letter, we have examined, considered and relied upon the following documents (collectively, the “Documents”):

1. the Registration Statement and the related form of prospectus contained therein, in the form in which it was transmitted to the Commission;

2. the Prospectus Supplement, in the form transmitted to the Commission for filing on December 18, 2023 pursuant to Rule 424(b)(5) under the Securities Act;

3. a copy of the Certificate of Incorporation of the Company, as filed with the Secretary of State of the State of Delaware on May 22, 2014;

4. the Bylaws of the Company;

5. resolutions adopted by the Board of Directors of the Company in respect of the issuance of the Shares; and

6. such other documents and matters of law as we have considered necessary or appropriate for the expression of the opinions contained herein.

December 18, 2023

Page 2

In rendering the opinions set forth below, we have assumed without investigation the following: (i) the genuineness of all signatures and the authenticity of all Documents submitted to us as originals, the conformity to authentic original documents of all Documents submitted to us as copies and the veracity of the Documents; (ii) each individual executing any of the Documents, whether on behalf of such individual or another person, is legally competent to do so; (iii) each of the parties (other than the Company) executing any of the Documents has duly and validly executed and delivered each of the Documents to which such party is a signatory; and (iv) the obligations of each party set forth in the Documents are valid and binding obligations of such party and are enforceable against such party in accordance with all stated terms.

As to various questions of fact material to this opinion, we have relied, to the extent we deemed reasonably appropriate, upon representations of officers or directors of the Company and upon documents, records and instruments furnished to us by the Company, without independently checking or verifying the accuracy of such documents, records and instruments.

Based upon the foregoing, and subject to the qualifications, assumptions and limitations set forth herein, we are of the opinion that the Shares have been duly authorized and validly issued and are fully paid and nonassessable.

This opinion letter is limited to the matters stated herein, and no opinions may be implied or inferred beyond the matters expressly stated herein. The opinions expressed herein are as of the date hereof, and we assume no obligation to update or supplement such opinions to reflect any facts or circumstances that may hereafter come to our attention or any changes in law that may hereafter occur. We do not express any opinion herein concerning any law other than the laws of the State of Delaware and the federal laws of the United States.

This opinion is being furnished to you for submission to the Commission as an exhibit to the Company’s Current Report on Form 8-K relating to the issuance of the Shares (the “Current Report”), which is incorporated by reference in the Registration Statement. We hereby consent to the filing of this opinion as an exhibit to the Current Report and such incorporation by reference into the Registration Statement, of which the Prospectus Supplement forms a part, and to the use of the name of our firm therein. In giving this consent, we do not admit that we are within the category of persons whose consent is required by Section 7 of the Securities Act or the rules and regulations of the Commission promulgated thereunder.

December 18, 2023

Page 3

Sincerely,

/s/ GREENBERG TRAURIG, P.A.