Exhibit 5.1

Greenberg Traurig, P.A.

401 E. Las Olas Blvd., Suite 2000

Ft. Lauderdale, FL 33301

June 7, 2023

Heritage Insurance Holdings, Inc.

1401 N. Westshore Blvd

Tampa, Florida 33607

Re: Registration Statement on Form S-8

Ladies and Gentlemen:

We have acted as counsel to Heritage Insurance Holdings, Inc., a Delaware corporation (the “Company”), in connection with the preparation and filing with the Securities and Exchange Commission of a Registration Statement on Form S-8 (the “Registration Statement”), under the Securities Act of 1933, as amended (the “Securities Act”). Such Registration Statement relates to the registration by the Company of 2,125,000 shares (the “Shares”) of the Company’s common stock, $0.0001 par value per share, issuable pursuant to the Heritage Insurance Holdings, Inc. 2023 Omnibus Incentive Plan (the “Plan”).

In so acting, we have examined, considered and relied upon copies of the following documents: (1) the Registration Statement, (2) the Company’s Certificate of Incorporation, (3) the Company’s By-laws, (4) the Plan, and (5) such other documents and instruments that we have deemed necessary for the expression of the opinions contained herein. In our examination of the aforesaid documents, we have assumed, without independent investigation, the genuineness of all signatures, the legal capacity of all individuals who have executed any of the documents, the authenticity of all documents submitted to us as originals and the conformity to the original documents of all copies.

As to matters of fact relevant to this opinion, we have relied solely upon our examination of the documents referred to above and have assumed the current accuracy and completeness of the information obtained from the documents referred to above and the representations and warranties made by representatives of the Company to us. We have made no independent investigation or other attempt to verify the accuracy of any of such information or to determine the existence or non-existence of any other factual matters.

Based upon and subject to the foregoing, we are of the opinion that the Shares have been duly authorized and, when issued and delivered by the Company in accordance with the Plan, will be validly issued, fully paid and non-assessable.

Our opinion expressed above is subject to the qualification that we express no opinion as to the applicability of, compliance with, or effect of any laws except the General Corporation Law of the State of Delaware.

We hereby consent to the filing of this opinion as an exhibit to the Registration Statement. In giving such consent, we do not thereby admit that we are included within the category of persons whose consent is required under Section 7 of the Securities Act or the rules and regulations promulgated thereunder.

Very truly yours,

/s/ Greenberg Traurig, P.A.

Greenberg Traurig, P.A.