Exhibit 5.1

March 9, 2009

The Colonial BancGroup, Inc.

100 Colonial Bank Blvd., 3rd floor

Montgomery, Alabama 36117

Re: The Colonial BancGroup, Inc., Post-Effective Amendment No. 2 to Registration Statement on Form S-3

Ladies and Gentlemen:

We have acted as counsel to The Colonial BancGroup, Inc., a Delaware corporation (the “Company”), in connection with the filing of the Post-Effective Amendment No. 2 to the Registration Statement (File No. 333-156253) (the “Registration Statement”) of the Company with the Securities and Exchange Commission (the “Commission”) under the Securities Act of 1933, as amended (the “Securities Act”).

The Registration Statement relates to the proposed issuance and sale from time to time pursuant to Rule 415 under the Securities Act of the following securities (the “Securities”): (i) shares of common stock, par value $2.50 per share (the “Common Stock”), of the Company; (ii) shares of preferred stock, par value $2.50 per share (the “Preferred Stock”) of the Company; (iii) senior debt securities of the Company (the “Senior Debt Securities”); (iv) subordinated debt securities of the Company (the “Subordinated Debt Securities”); and, collectively with the Senior Debt Securities, (the “Debt Securities”); and (v) warrants to purchase Debt Securities, Preferred Stock, Common Stock or other securities of the Company or another issuer (the “Warrants”), which will be issued pursuant to a warrant agreement (the “Warrant Agreement”) to be entered into by the Company and a warrant agent (the “Warrant Agent”). The Securities may be offered in separate series, in amounts, at prices, and on terms to be set forth in the prospectuses and one or more supplements to the prospectuses (collectively, the “Prospectuses”) constituting a part of the Registration Statement, and in the Registration Statement. The aggregate public offering price of the Securities being registered will be $840,000,000.

Each series of Senior Debt Securities will be issued under a separate indenture for senior debt (as amended or supplemented from time to time, the “Senior Indenture”), by and between the Company and The Bank of New York Trust Company, N. A., as trustee (the “Trustee”), a form of which was filed as Exhibit 4.1 to the original Registration Statement. Each series of Subordinated Debt Securities will be issued under a separate indenture for subordinated debt (as amended or supplemented from time to time, the “Subordinated Indenture,” together with the Senior Indenture, the “Indentures”), by and between the Company and The Bank of New York Trust Company, N. A., as trustee, a form of which was filed as Exhibit 4.2 to the original Registration Statement.

Each series of Preferred Stock is to be issued under the Amended and Restated Certificate of Incorporation, as amended, of the Company (the “Certificate of Incorporation”) and a certificate of designations (a “Certificate of Designations”) to be approved by the board of directors of the Company or a committee thereof (“Board of Directors”) and filed with the Secretary of State of the State of Delaware (the “Delaware Secretary of State”) in accordance with Section 151 of the General Corporation Law of the State of Delaware. The Common Stock is to be issued under the Certificate of Incorporation.

As counsel to the Company, we have examined relevant corporate and other documents, and made such other examinations of matters of law and of fact as we have considered appropriate or advisable for purposes of this opinion. In our examination, we have assumed the genuineness of all signatures, the legal capacity of all natural persons, the authenticity of all documents submitted to us as original documents and the conformity to original documents of all documents submitted to us as certified, conformed, facsimile, electronic or photostatic copies. We have also assumed that the Company has been duly organized and is validly existing under the laws of the State of Delaware. As to questions of fact material to this opinion, we have relied upon the statements as to factual matters contained in the Registration Statement and statements of officers of the Company, and we have made no independent investigation with regard thereto. In addition, we have assumed that any samples of documents submitted to us will be executed without any alterations made thereto.

To the extent that the obligations of the Company under any agreement, the Warrant Agreement or Indenture may be dependent upon such matters, we assume for purposes of this opinion that: (i) the other party or parties to such agreement or Indenture is duly organized, validly existing and in good standing under the laws of its jurisdiction of organization; (ii) the other party or parties to such agreement or Indenture is duly qualified to engage in the activities contemplated by the agreement, the Warrant Agreement or Indenture, as applicable; (iii) the agreement or Indenture has been duly authorized, executed and delivered by the other party or parties to such agreement or Indenture, as applicable, and constitutes the valid and binding obligation of the other party or parties to such agreement or Indenture, as applicable, enforceable against the other party or parties to such agreement or Indenture, as applicable, in accordance with its terms; (iv) the other party or parties to such agreement, Warrant Agreement or Indenture is in compliance, with respect to any actions the other party to such agreement or Indenture may take under such agreement or Indenture, as applicable, with all applicable laws and regulations; and (v) the other party or parties to such agreement, Warrant Agreement or Indenture has the requisite organizational and legal power and authority to perform its obligations under such agreement or Indenture, as applicable.

For purposes of this opinion, the term “Enforceability Exceptions” shall mean any (A) bankruptcy, insolvency, reorganization, fraudulent transfer, moratorium and other similar laws now or hereafter in effect relating to or affecting creditors’ rights generally and (B) general principles of equity (regardless of whether considered in a proceeding at law or in equity), including the following concepts: (i) principles governing the availability of specific performance, injunctive relief or other traditional equitable remedies; (ii) principles affording traditional equitable defenses (e.g., waiver, laches and estoppel); (iii) good faith and fair dealing; (iv) reasonableness; (v) materiality of the breach; (vi) impracticability or impossibility of

2

performance; (vii) the effect of obstruction or failure to perform or otherwise act in accordance with an agreement by any person other than the Company; and (viii) unconscionability.

Based upon the foregoing and subject to the limitations, qualifications, exceptions and assumptions set forth herein, it is our opinion that:

1. The Common Stock, when (A) the Board of Directors has taken all necessary corporate action to approve the issuance and terms of the offering of the shares of the Common Stock, whether in certificated or uncertificated form, and related matters, in each case so as not to violate any applicable law or any agreement or instrument to which the Company is a party or by which it is bound, and (B) if such Common Stock is in certificated form, certificates representing the shares of Common Stock have been duly executed, countersigned, registered and delivered either (i) in accordance with the applicable definitive purchase, underwriting or similar agreement approved by the Board of Directors upon payment of the consideration therefor (not less than the par value of the Common Stock) provided for therein or (ii) upon conversion or exercise of any Securities, in accordance with the terms of such Securities or the instrument governing such Securities providing for such conversion or exercise as approved by the Board of Directors, upon receipt of the consideration approved by the Board of Directors therefor (not less than the par value of the Common Stock), will be validly issued, fully paid and nonassessable.

2. The Preferred Stock, when (A) the Board of Directors has taken all necessary corporate action to designate the relevant rights, preferences, privileges, limitations or restrictions of the Preferred Stock and to approve the issuance and terms of the offering of the shares of the Preferred Stock, whether in certificated or uncertificated form, and related matters, in each case so as not to violate any applicable law or any agreement or instrument to which the Company is a party or by which it is bound, including the adoption of a Certificate of Designations and the filing of the Certificate of Designations with the Secretary of State of the State of Delaware, and (B) if such Preferred Stock is in certificated form, certificates representing the shares of Preferred Stock have been duly executed, countersigned, registered and delivered either (i) in accordance with the applicable definitive purchase, underwriting or similar agreement approved by the Board of Directors upon payment of the consideration therefor (not less than the par value of the Preferred Stock) provided for therein or (ii) upon conversion or exercise of any Securities, in accordance with the terms of such Securities or the instrument governing such Securities providing for such conversion or exercise as approved by the Board of Directors, upon receipt of the consideration approved by the Board of Directors therefor (not less than the par value of the Preferred Stock), will be validly issued, fully paid and nonassessable.

3. Each series of the Senior Debt Securities and Subordinated Debt Securities of the Company, when duly established pursuant to the terms of the Indenture under which they are issued, in each case so as not to violate any applicable law or any agreement or instrument to which the Company is a party or by which it is bound, and duly executed, authenticated and issued as provided in the applicable Indenture and delivered against payment therefor, will constitute valid and legally binding obligations of the Company entitled to the benefits of the Indenture under which the obligations are issued, subject to the Enforceability Exceptions.

4. When the Company and a Warrant Agent execute and deliver a Warrant Agreement and the specific terms of a particular Warrant have been duly authorized and established in

3

accordance with such Warrant Agreement, and such Warrant has been duly authorized, executed, countersigned, issued and delivered in accordance with such Warrant Agreement, against payment therefore in accordance with the applicable underwriting or other agreement, such Warrant will constitute the valid and binding obligation of the Company.

In rendering the foregoing opinions, we have further assumed that: (i) all Securities will be issued and sold in compliance with applicable law; (ii) the Securities will be sold and delivered to, and paid for by, the purchasers at the price and in accordance with the terms of an agreement or agreements duly authorized and validly executed and delivered by the parties thereto; (iii) the Company will authorize the offering and issuance of the Securities and will authorize, approve and establish the final terms and conditions thereof and will take any other appropriate additional corporate action; and (iv) certificates or other instruments or documents, if any, representing the Securities will be duly executed and delivered and, to the extent required by the applicable Indenture, duly authenticated and countersigned.

We are expressing no opinion as to any obligations that parties other than the Company may have under or in respect of the Securities or as to the effect that their performance of such obligations may have upon any of the matters referred to above.

The foregoing opinions are limited to the laws of the States of Alabama and New York as it relates to the enforceability of documents, agreements and instruments referred to herein, the General Corporation Law of the State of Delaware, applicable provisions of the Constitution of the State of Delaware and reported judicial decisions interpreting such General Corporation Law and Constitution, and federal laws of the United States of America to the extent referred to specifically herein. We do not express any opinion herein concerning any other laws, statutes, ordinances, rules or regulations. We are not rendering any opinion as to compliance with any federal or state law, rule, or regulation relating to securities, or to the sale or issuance thereof.

This opinion letter is delivered to the addressees hereof solely for their use in connection with the transactions and matters contemplated by the Registration Statement and the Securities and may not be used, circulated, quoted or otherwise relied upon by any other person or for any other purpose, and may not be disclosed, quoted, filed with a governmental agency or otherwise referred to without our prior written consent. No opinion may be implied or inferred beyond the opinion expressly stated in the numbered paragraphs above. Our opinions expressed herein are as of the date hereof, and we hereby expressly disclaim any obligation to supplement this opinion for any changes that may occur after the date hereof with respect to any matters of fact or law addressed herein.

We hereby consent to the filing of this opinion letter as an exhibit to the Post-Effective Amendment No. 2 to the Registration Statement and to the use of our name under the heading “Validity of the Securities” in the Prospectus constituting a part thereof. In giving such consent, we do not thereby admit that we are within the category of persons whose consent is required under Section 7 of the Securities Act or the rules and regulations of the Commission thereunder.

Sincerely,

/s/ Balch & Bingham LLP

4