Exhibit 5.1

March 14, 2024

Heritage Insurance Holdings, Inc.

1401 N Westshore Blvd.

Tampa, FL 33607

Re: Heritage Insurance Holdings, Inc. Registration Statement on Form S-3

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 statement on Form S-3 to be filed by the Company with the Securities and Exchange Commission (the “Commission”) on or about the date hereof (the “Registration Statement”), in connection with the registration under the Securities Act of 1933, as amended (the “Securities Act”), and the proposed offer, issuance and sale from time to time on a delayed or continuous basis pursuant to Rule 415 under the Securities Act, as set forth in the Registration Statement, the base prospectus contained therein (the “Base Prospectus”) and any supplement to the Base Prospectus (each, a “Prospectus Supplement”, and together with the Base Prospectus, a “Prospectus”), of the following securities of the Company:

(i) shares of common stock of the Company, par value $0.0001 per share (the “Common Stock”);

(ii) shares of preferred stock of the Company, par value $0.0001 per share (the “Preferred Stock”);

(iii) senior debt securities, in one or more series (the “Senior Debt Securities”), which will be issued under a Senior Indenture, a form of which is filed as an exhibit to the Registration Statement (as amended or supplemented, the “Senior Indenture”), to be entered into by and between the Company and the trustee named therein (the “Senior Indenture Trustee”);

(iv) subordinated debt securities, in one or more series (the “Subordinated Debt Securities” and, together with the Senior Debt Securities, the “Debt Securities”), which will be issued under a Subordinated Indenture, a form of which is filed as an exhibit to the Registration Statement (as amended or supplemented, the “Subordinated Indenture” and, together with the Senior Indenture, the “Indentures”), to be entered into by and between the Company and the trustee named therein (the “Subordinated Indenture Trustee” and, together with the Senior Indenture Trustee, each a “Trustee” and, collectively, the “Trustees”);

(v) warrants to purchase the Common Stock, the Preferred Stock or the Debt Securities (the “Warrants”), which will be issued pursuant to a warrant agreement, which will be filed at a later date by amendment or as an exhibit to a document incorporated by reference into the Registration Statement, to be entered into by and between the Company and a bank or trust company as warrant agent;

March 14, 2024

Page 2

(vi) subscription rights to purchase the Common Stock, the Preferred Stock, the Debt Securities or other securities (the “Subscription Rights”);

(vii) stock purchase contracts for the purchase of shares of the Common Stock (the “Stock Purchase Contracts”); and

(viii) stock purchase units consisting of a Stock Purchase Contract and either Debt Securities or debt obligations of third parties, including U.S. Treasury securities (the “Stock Purchase Units” and, together with the Common Stock, the Preferred Stock, the Debt Securities, the Warrants, the Subscription Rights and the Stock Purchase Contracts, the “Securities”).

This opinion letter is being furnished in accordance with the requirements of Item 601(b)(5) of Regulation S-K under the Securities Act.

We have made such legal and factual examinations and inquiries, including an examination of originals or copies certified or otherwise identified to our satisfaction of such documents, corporate records and instruments, as we have deemed necessary or appropriate for purposes of this opinion letter. In our examination, we have assumed the genuineness of all signatures, the authenticity of all documents submitted to us as originals and the conformity to authentic original documents of all documents submitted to us as copies. As to facts material to the opinions, statements and assumptions expressed herein, we have relied upon oral or written statements and representations of officers and other representatives of the Company and others. We have not independently verified such factual matters.

In expressing our opinions below, we have assumed that:

1. the Registration Statement (including any and all required post-effective amendments thereto) will have become effective under the Securities Act and will comply with all applicable laws;

2. the Registration Statement (including any and all required post-effective amendments thereto) will be effective under the Securities Act and will comply with all applicable laws at the time the Securities are offered or sold as contemplated by the Registration Statement (including any and all required post-effective amendments thereto), the Base Prospectus, and the applicable Prospectus Supplement(s);

3. no stop order suspending the effectiveness of the Registration Statement (including any and all required post-effective amendments thereto) will have been issued and remain in effect;

4. a Prospectus Supplement describing the Securities offered thereby and the offering thereof and complying with all applicable laws will have been prepared and filed with the Commission;

March 14, 2024

Page 3

5. the Securities will be offered and sold in the form and with the terms set forth in the Registration Statement (including any and all required post-effective amendments thereto), the Base Prospectus, and the applicable Prospectus Supplement(s) and the organizational documents of the Company, as applicable;

6. the Securities will be offered and sold in compliance with all applicable federal and state securities laws and in the manner stated in the Registration Statement (including any and all required post-effective amendments thereto), the Base Prospectus, and the applicable Prospectus Supplement(s);

7. the Company will have obtained any and all legally required consents, approvals, authorizations and other orders of the Commission and any and all other regulatory authorities and other third parties necessary to offer and sell the Securities being offered;

8. a definitive purchase, underwriting, sales or similar agreement (each a “Purchase Agreement”) with respect to any Securities offered and sold will have been duly authorized and validly executed and delivered by the Company and the other parties thereto;

9. the Indentures will have been duly authorized and validly executed and delivered by the Company and the other parties thereto; and

10. any Securities or other securities issuable upon conversion, exchange or exercise of any Security being offered and sold will be duly authorized, created and, if appropriate, reserved for issuance upon such conversion, exchange or exercise.

Our opinions expressed in paragraphs 3, 4, 5, 6 and 7 below are subject to the qualifications that we express no opinion as to the applicability of, compliance with or effect of: (i) any bankruptcy, insolvency, reorganization, preference, fraudulent conveyance, fraudulent transfer, moratorium or other similar laws relating to or affecting the rights and remedies of creditors generally (including, without limitation, Sections 547 and 548 of the United States Bankruptcy Code and Article 10 of the New York Debtor and Creditor Law); (ii) general principles of equity, whether considered in a proceeding in equity or at law (including the possible unavailability of specific performance or injunctive relief), concepts of materiality, reasonableness, good faith and fair dealing, and the discretion of the court before which a proceeding is brought; or (iii) public policy considerations that may limit the rights of parties to obtain certain remedies.

We express no opinion as to (i) any provision providing for the indemnification of or contribution to a party with respect to a liability where such indemnification or contribution is contrary to public policy, (ii) consents to, or restrictions upon, governing law, jurisdiction, venue, arbitration, remedies or judicial relief, (iii) the securities or “Blue Sky” laws of any state to the offer or sale of the Securities and (iv) the antifraud provisions of the securities or other laws of any jurisdiction.

March 14, 2024

Page 4

Subject to the foregoing and the other matters set forth herein, it is our opinion that, as of the date hereof:

1. With respect to the offer and sale of Common Stock, when (a) an issuance of Common Stock has been duly authorized by all necessary corporate action of the Company and (b) the shares of Common Stock have been issued, delivered and paid for in an amount not less than the par value thereof in the manner contemplated by the applicable Prospectus and by such corporate action and either in accordance with the applicable Purchase Agreement or upon conversion, exchange or exercise of any other security, in accordance with the terms of such security or the instrument governing such security providing for such conversion, exchange or exercise as approved by the board of directors of the Company (the “Board”), and (c) the total amounts and numbers of shares of Common Stock issued do not exceed the respective total amounts and numbers of shares (i) available under the Company’s certificate of incorporation (as amended, the “Certificate of Incorporation”) and (ii) authorized by the Board in connection with the offering contemplated by the applicable Prospectus, such shares of Common Stock will be validly issued, fully paid and nonassessable.

2. With respect to any series of Preferred Stock, when (a) a series of Preferred Stock has been duly established in accordance with the terms of the Certificate of Incorporation and authorized by all necessary corporate action of the Company, including the adoption of a resolution establishing and designating the series and fixing and determining the preferences, limitations and relative rights thereof and the filing of a certificate of designation with respect to the series with the Secretary of State as required under the General Corporation Law of the State of Delaware (the “DGCL”), (b) the shares of Preferred Stock have been issued, delivered and paid for in an amount not less than the par value thereof in the manner contemplated by the applicable Prospectus and by such corporate action and either in accordance with the applicable Purchase Agreement or upon conversion, exchange or exercise of any other security, in accordance with the terms of such security or the instrument governing such security providing for such conversion, exchange or exercise as approved by the Board, and (c) the total amounts and numbers of shares of Preferred Stock issued do not exceed the respective total amounts and numbers of shares (i) available under the Certificate of Incorporation and (ii) authorized by the Board in connection with the offering contemplated by the applicable Prospectus, such shares of such series of Preferred Stock will be validly issued, fully paid and nonassessable.

3. With respect to the Debt Securities to be issued under an Indenture, when (a) the Trustee has duly executed and delivered the applicable Indenture, (b) the applicable Indenture has been duly authorized by all necessary corporate action of the Company (including, without limitation, the adoption by the Board of a resolution in form and content as required by applicable law duly authorizing the execution and delivery of such Indenture) and duly executed and delivered by the Company, (c) the applicable Indenture has been duly qualified under the Trust Indenture Act of 1939, as amended, (d) the specific terms of a particular issuance of Debt Securities have been duly established in accordance with such Indenture, if any, and all applicable law and authorized by all necessary corporate action of the Company (including, without limitation, the adoption by the Board of a resolution in form and content as required by applicable law duly authorizing the issuance and delivery of the Debt Securities), and (e) the Debt Securities have been duly executed, authenticated, issued and delivered against payment therefor in accordance with the provisions of the applicable Indenture and the applicable definitive Purchase Agreement upon payment of the consideration therefor provided for therein, such Debt Securities will be legally valid and binding obligations of the Company, enforceable against the Company in accordance with their terms.

March 14, 2024

Page 5

4. With respect to the Warrants, when (a) a warrant agreement, if any, has been duly authorized by all necessary corporate action of the Company (including, without limitation, the adoption by the Board of a resolution in form and content as required by applicable law duly authorizing the execution and delivery of such warrant agreement) and duly executed and delivered by the Company, (b) the specific terms of a particular issuance of Warrants have been duly established in accordance with such warrant agreement, if any, and all applicable law and authorized by all necessary corporate action of the Company (including, without limitation, the adoption by the Board of a resolution in form and content as required by applicable law duly authorizing the issuance and delivery of the Warrants), and (c) the Warrants have been duly executed, issued and delivered against payment therefor in accordance with such warrant agreement, if any, the applicable Purchase Agreement and all applicable law (and assuming the satisfaction of the conditions described in the applicable numbered paragraphs of this opinion letter with respect to our opinion regarding any Securities issuable upon exercise of the Warrants), such Warrants will be legally valid and binding obligations of the Company, enforceable against the Company in accordance with their terms.

5. With respect to the Subscription Rights, when (a) a subscription rights agreement, if any, has been duly authorized by all necessary corporate action of the Company (including, without limitation, the adoption by the Board of a resolution in form and content as required by applicable law duly authorizing the execution and delivery of such subscription rights agreement) and duly executed and delivered by the Company, (b) the specific terms of a particular issuance of Subscription Rights have been duly established in accordance with such subscription rights agreement, if any, and all applicable law and authorized by all necessary corporate action of the Company (including, without limitation, the adoption by the Board of a resolution in form and content as required by applicable law duly authorizing the issuance and delivery of the Subscription Rights), and (c) the Subscription Rights have been duly executed, issued and delivered against payment therefor in accordance with such subscription rights agreement, if any, the applicable Purchase Agreement and all applicable law (and assuming the satisfaction of the conditions described in the applicable numbered paragraphs of this opinion letter with respect to our opinion regarding any Securities issuable pursuant to the subscription rights agreement), such Subscription Rights will be legally valid and binding obligations of the Company, enforceable against the Company in accordance with their terms.

6. With respect to the Stock Purchase Contracts, when (a) a purchase agreement, if any, relating to the Stock Purchase Contracts has been duly authorized by all necessary corporate action of the Company (including, without limitation, the adoption by the Board of a resolution in form and content as required by applicable law duly authorizing the execution and delivery of such purchase agreement) and duly executed and delivered by the Company, (b) the specific terms of a particular issuance of Stock Purchase Contracts have been duly established in accordance with such purchase agreement, if any, and all applicable law and authorized by all necessary corporate action of the Company (including, without limitation, the adoption by the Board of a resolution in form and content as required by applicable law duly authorizing the issuance and delivery of the Stock Purchase Contracts), and (c) the Stock Purchase Contracts have been duly executed, issued and delivered against payment therefor in accordance with such purchase agreement, if any, the applicable Purchase Agreement and all applicable law (and assuming the satisfaction of the conditions described in the applicable numbered paragraphs of this opinion letter with respect to our opinion regarding any Securities issuable pursuant to the purchase agreement), such Stock Purchase Contracts will be legally valid and binding obligations of the Company, enforceable against the Company in accordance with their terms.

March 14, 2024

Page 6

7. With respect to the Stock Purchase Units, when (a) a purchase agreement, if any, has been duly authorized by all necessary corporate action of the Company (including, without limitation, the adoption by the Board of a resolution in form and content as required by applicable law duly authorizing the execution and delivery of such purchase agreement) and duly executed and delivered by the Company, (b) the specific terms of a particular issuance of Stock Purchase Units have been duly established in accordance with such purchase agreement, if any, and all applicable law and authorized by all necessary corporate action of the Company (including, without limitation, the adoption by the Board of a resolution in form and content as required by applicable law duly authorizing the issuance and delivery of the Stock Purchase Units), and (c) the Stock Purchase Units have been duly executed, issued and delivered against payment therefor in accordance with such purchase agreement, if any, the applicable Purchase Agreement and all applicable law (and assuming the satisfaction of the conditions described in the applicable numbered paragraphs of this opinion letter with respect to our opinion regarding any Securities issuable pursuant to the purchase agreement), such Stock Purchase Units will be legally valid and binding obligations of the Company, enforceable against the Company in accordance with their terms.

This opinion letter is opining upon and is limited to the state laws of the State of New York and the Delaware General Corporation Law as such laws presently exist and to facts as they presently exist. We express no opinion with respect to the effect or applicability of the laws of any other jurisdiction.

This opinion letter is being delivered solely for the benefit of the Company and such other persons as are entitled to rely upon it pursuant to applicable provisions of the Securities Act. This opinion letter may not be used, quoted, relied upon or referred to for any other purpose nor may this opinion letter be used, quoted, relied upon or referred to by any other person, for any purpose, without our prior written consent.

We consent to the filing of this opinion letter as an exhibit to the Registration Statement and to the reference to our firm in the applicable Prospectus under the heading “Legal Matters.” 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 or the rules and regulations of the Commission thereunder.

Yours very truly,

/s/ Greenberg Traurig, P.A.