EXHIBIT 5.1

SHUTTS & BOWEN LLP

201 SOUTH BISCAYNE BLVD.

1500 MIAMI CENTER

MIAMI, FLORIDA 33131

June 5, 2012

OptimumBank Holdings, Inc.

2477 East Commercial Blvd.

Fort Lauderdale, FL 33308

Ladies and Gentlemen:

We have acted as counsel to OptimumBank Holdings, Inc, a Florida corporation (the “Company”), in connection with the preparation of the Company’s pre-effective amendment to the registration statement on Form S-1 (File No. 333-179537) (the “Registration Statement”) under the Securities Act of 1933, as amended (the “Securities Act”), filed by the Company with the Securities and Exchange Commission (the “Commission”) on the date hereof.

The Registration Statement relates to the proposed offer and sale from time to time by the selling stockholders identified in the Registration Statement (the “Selling Stockholders”) of up to 13,496,000 shares of Common Stock (the “Shares”). The Shares will be offered in amounts, at prices and on terms to be determined at the time of sale and to be set forth in supplements to the prospectus (each a “Prospectus Supplement”) contained in the Registration Statement.

We have examined originals or copies, certified or otherwise identified to our satisfaction, of (i) the Articles of Incorporation of the Company, as amended to date (the “Articles of Incorporation”), (ii) the Bylaws of the Company, as amended to date (the “Bylaws”), (iii) the Registration Statement and all exhibits thereto, (iv) the minutes and records of the corporate proceedings of the Company with respect to the filing of the Registration Statement, (v) the minutes and records of the corporate proceedings of the Company with respect to the issuance of the Shares to the Selling Stockholders, (vi) the specimen Common Stock certificate, and (vii) such other certificates, statutes, instruments and documents as we considered appropriate for purposes of the opinions hereafter expressed.

In making the foregoing examinations, we have assumed the genuineness of all signatures, the authenticity of all documents submitted to us as originals, the conformity to original documents submitted to us as certified, conformed or photostatic copies thereof and the authenticity of the originals of such latter documents.

As to various questions of fact material to the opinions expressed below, we have, without independent third party verification of their accuracy, relied in part, and to the extent we deemed reasonably necessary or appropriate, upon the representations and warranties of the Company contained in such documents, records, certificates, instruments or representations furnished or made available to us by the Company.

OptimumBank Holdings, Inc.

June 5, 2012

Page 2

In connection with this opinion, we have assumed that (i) the Company will continue to be incorporated and in good standing under the Florida Business Corporation Act (the “FBCA”); (ii) the Registration Statement and any amendments thereto (including post-effective amendments) will have become effective and will remain effective; (iii) a Prospectus Supplement will have been prepared and filed with the Commission properly describing the Shares offered thereby in accordance with all applicable requirements; (iv) no stop order of the Commission preventing or suspending the use of the prospectus contained in the Registration Statement or any Prospectus Supplement will have been issued; (v) the prospectus contained in the Registration Statement and any required Prospectus Supplement will have been delivered to the purchaser of the Shares as required in accordance with applicable law; (vi) the resolutions of the Company referred to below will not have been modified or rescinded, (vii) there will not have occurred any change in the law affecting the authorization, execution, delivery, validity, enforceability or fully paid status of the Common Stock, and (vii) all Shares will be sold in compliance with the Articles of Incorporation, the Bylaws and applicable federal, state and other laws, including the FBCA, and in the manner stated in the Registration Statement, or any amendment thereto, and any applicable Prospectus Supplement.

Based on the foregoing and subject to the limitations, qualifications, exceptions and assumptions set forth herein and having due regard for such legal considerations as we deem relevant, we are of the opinion that the Shares are validly issued, fully paid and non-assessable.

The opinions expressed herein are limited to the FBCA, as currently in effect, and judicial decisions reported as of the date hereof and interpreting the FBCA.

This opinion (i) is rendered in connection with the filing of the Registration Statement, (ii) is rendered as of the date hereof, and we undertake no, and hereby disclaim any kind of, obligation to advise you of any change or any new developments that might affect any matters or opinions set forth herein, and (iii) is limited to the matters stated herein and no opinions may be inferred or implied beyond the matters expressly stated herein.

We hereby consent to the filing of this opinion as an exhibit to the Registration Statement and to the references to our Firm’s name therein. In giving the foregoing consent, we do not admit that we are in the category of persons whose consent is required under Section 7 of the Securities Act, or the rules and regulations of the Commission promulgated thereunder.