Exhibit 5.1

35 W. Wacker Drive Chicago, IL 60601 T +1 312 558 5600 T +1 312 558 5700

December 1, 2017

Heritage Insurance Holdings, Inc.

2600 McCormick Drive, Suite 300

Clearwater, FL 33759

Re: Form S-3 Registration Statement

Ladies and Gentlemen:

We have acted as special counsel to Heritage Insurance Holdings, Inc., a Delaware corporation (the “Company”), in connection with the Company’s registration statement on Form S-3 filed with the Securities and Exchange Commission (the “Commission”) on or about the date hereof (the “Registration Statement”), under the Securities Act of 1933, as amended (the “Securities Act”). The Registration Statement relates to the registration of the offer and sale by the selling stockholders set forth in the prospectus contained in the Registration Statement or any supplement to the prospectus that may be filed under the Securities Act of 2,222,215 shares of common stock, par value $0.001 per share (the “Shares”), of the Company.

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

In rendering the opinion set forth below, we have examined and relied upon such certificates, corporate records, agreements, instruments and other documents, and examined such matters of law, that we considered necessary or appropriate as a basis for the opinion, including (i) the certificate of incorporation of the Company, as amended, as in effect on the date hereof, (ii) the by-laws of the Company, as in effect on the date hereof, and (iii) resolutions of the Board of Directors of the Company relating to, among other matters, the issuance of the Shares. In our examination, we have assumed the legal capacity of all natural persons, the genuineness of all signatures, the authenticity of all documents submitted to us as originals, the conformity to original documents of all documents submitted to us as certified or photostatic copies and the authenticity of the originals of such latter documents. As to any facts material to the opinion expressed herein that we did not independently establish or verify, we have relied upon oral or written statements and representations of officers and other representatives of the Company and others.

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

The opinion expressed herein is based upon and limited to the General Corporation Law of the State of Delaware, including the statutory provisions, the applicable provisions of the Delaware Constitution and reported judicial decisions interpreting the foregoing. We express no opinion herein as to any other laws, statutes, regulations or ordinances.

Page 2

We hereby consent to the filing of this opinion letter as Exhibit 5.1 to the Registration Statement and to the reference to our firm under the caption “Legal Matters” in the prospectus included in the Registration Statement. In giving such consent, we do not thereby admit that we are experts within the meaning of the Securities Act or the rules and regulations of the Commission or that this consent is required by Section 7 of the Securities Act.

Very truly yours,

/s/ Winston & Strawn LLP