Exhibit 5.1

August 6, 2014

Heritage Insurance Holdings, Inc.

2600 McCormick Drive, Suite 300

Clearwater, Florida 33759

Re: Form S-8 Registration Statement

Ladies and Gentlemen:

We have acted as special counsel for Heritage Insurance Holdings, Inc., a Delaware corporation (the “Company”), in connection with the registration on Form S-8 (the “Registration Statement”) of the offer and sale of up to 2,981,737 shares (the “Shares”) of the Company’s common stock, par value $0.0001 per share (the “Common Stock”), to be issued pursuant to plan awards (the “Plan Awards”) under the Heritage Insurance Holdings, Inc. Omnibus Incentive Plan (the “Plan”).

This opinion letter is delivered in accordance with the requirements of Item 601(b)(5) of Regulation S-K promulgated under the Securities Act of 1933, as amended (the “Act”).

In connection with this opinion, we have examined and are familiar with originals or copies, certified or otherwise identified to our satisfaction, of: (i) the Registration Statement, as filed with the Securities and Exchange Commission (the “Commission”) under the Act; (ii) the Certificate of Incorporation of the Company, as currently in effect; (iii) the By-Laws of the Company, as currently in effect; (iv) the Plan; and (v) resolutions of the Board of Directors of the Company relating to, among other things, the reservation for issuance of the Shares, the filing of the Registration Statement and the approval of the Plan. We have also examined such other documents as we have deemed necessary or appropriate as a basis for the opinion set forth below.

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 certified or photostatic copies and the authenticity of the originals of such latter documents. We have also assumed that the Company’s Board of Directors, or a duly authorized committee thereof, will have approved each Plan Award prior to the issuance thereof. As to any facts material to this opinion which 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 and subject to the foregoing, we are of the opinion that the Shares have been duly authorized by the requisite corporate action on the part of the Company and, when issued, paid for and delivered pursuant to the terms and in the manner set forth in the Plan, and assuming that the Shares remain duly reserved for issuance within the limits of the Common Stock then remaining authorized but unissued, will be validly issued, fully paid and nonassessable.

The foregoing opinion is 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. This opinion is given as of the date hereof and we assume no obligation to update or supplement such opinion to reflect any facts or circumstances that may hereafter come to our attention or any changes that may hereafter occur.

We hereby consent to the filing of this opinion with the Commission as an exhibit to the Registration Statement. In giving such consent, we do not concede that we are experts within the meaning of the Act or the rules and regulations thereunder or that this consent is required by Section 7 of the Act or the rules and regulations of the Commission.

Very truly yours,

/s/ Winston & Strawn LLP