Exhibit 5.1

United Insurance Holdings Corp.

360 Central Avenue, Suite 900

St. Petersburg, Florida 33701

Ladies and Gentlemen:

We have acted as counsel to United Insurance Holdings Corp., a Delaware corporation (the “Company”), in connection with the preparation of a Registration Statement on Form S-1 (as amended, the “Registration Statement”), including the prospectus constituting a part thereof (the “Prospectus”), filed by the Company with the Securities and Exchange Commission under the Securities Act of 1933, as amended (the “Securities Act”), relating to the proposed issuance and offering by the Company of up to 5,750,000 shares of the Company’s common stock, $0.0001 par value per share (the “Common Stock”), and the proposed offering by the selling stockholders named therein (the “Selling Stockholders”) of up to 300,075 shares of Common Stock.

In connection with this opinion, we have examined and relied upon the following:

(a) The Registration Statement, including the Prospectus;

(b) The Company’s Second Amended and Restated Certificate of Incorporation, as amended;

(c) The Company’s Bylaws;

(d) The resolutions of the Company’s Board of Directors relating to the authorization of the issuance of the shares of Common Stock covered by the Registration Statement; and

(e) Such other proceedings, documents and records as we have deemed necessary to enable us to render this opinion.

In giving this opinion, we have assumed that any certificates representing the shares of Common Stock to be offered and sold by the Selling Stockholders or the Company that are covered by the Registration Statement conform to the Specimen Common Stock Certificate filed as Exhibit 4.1 to the Registration Statement.

Based upon the foregoing, and in reliance thereon, we are of the opinion that:

1. The shares of Common Stock covered by the Registration Statement to be offered and sold by the Selling Stockholders have been validly issued and are fully paid and nonassessable.

2. The shares of Common Stock covered by the Registration Statement to be offered and sold by the Company, when the price and the other terms of sale thereof have been determined by action of the Special Committee designated by the Company’s Board of

United Insurance Holdings Corp.

December 3, 2012

Page 2

Directors in the manner contemplated by and as authorized by the Company’s Board of Directors, and when issued and paid for in the manner contemplated in the Registration Statement and the Prospectus, will be validly issued, fully paid and nonassessable.

We consent to the reference to our firm under the caption “Legal Matters” in the Prospectus and to the filing of this opinion as an exhibit to the Registration Statement. In giving this consent, we do not admit that we are “experts” within the meaning of Section 11 of the Securities Act or within the category of persons whose consent is required under Section 7 of the Securities Act.

Very truly yours,

/s/ Foley & Lardner LLP