Exhibit 5.1

[FORM OF OPINION TO BE RECEIVED FROM COUNSEL]

May [__], 2014

Heritage Insurance Holdings, Inc.

2600 McCormick Drive, Suite 300

Clearwater, Florida 33759

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-1 (Registration No. 333-195409) initially filed with the Securities and Exchange Commission (the “Commission”) on April 21, 2014, as amended to date (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 of up to 6,900,000 shares of the Company’s common stock, par value $0.0001 per share (the “Common Stock”), including up to 900,000 shares of Common Stock that may be offered and sold by the Company to cover over-allotments pursuant to the Registration Statement (together, the “Shares”).

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 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 the Certificate of Incorporation of the Company filed as Exhibit 3.2 to the Registration Statement, to be filed with the Secretary of State of the State of Delaware prior to the sale 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, when the Shares are delivered to the Company’s underwriters against payment of the agreed consideration therefor in accordance with the underwriting agreement, the Shares will be validly issued, fully paid and nonassessable.

Heritage Insurance Holdings, Inc.

May [__], 2014

Page 2

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.

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,

Winston & Strawn LLP