Exhibit 5.8

[Letterhead of Sullivan and Cromwell LLP]

September 11, 2012

Bancolombia S.A.,

Carrera 48# 26-85, Avenida Los Industriales,

Medellín,

Colombia.

Ladies and Gentlemen:

In connection with the registration under the Securities Act of 1933 (the “Act”) of U.S.$1,200 million aggregate principal amount of 5.125% Subordinated Notes due 2022 (the “Notes”) of Bancolombia S.A., a corporation organized as a sociedad anónima under the laws of the Republic of Colombia (the “Bank”) we, as your United States counsel, have examined such corporate records, certificates and other documents, and such questions of law, as we have considered necessary or appropriate for the purposes of this opinion.

Upon the basis of such examination, we advise you that, in our opinion, the Notes constitute valid and legally binding obligations of the Bank, subject to bankruptcy, insolvency, fraudulent transfer, reorganization, moratorium and similar laws of general applicability relating to or affecting creditors’ rights and to general equity principles.

The foregoing opinion is limited to the federal laws of the United States and the laws of the State of New York, and we are expressing no opinion as to the effect of the laws of any other jurisdiction. For the purposes of our opinion we have assumed that the Bank has been duly incorporated and is an existing corporation (sociedad anónima) under the laws of the Republic of Colombia, and that any document referred to in this opinion and executed by the Bank has been duly authorized, executed and delivered insofar as the laws of the Republic of Colombia are concerned. With respect to all matters of Colombian law, we note that you are being provided with the opinion, dated the date hereof, of Gómez-Pinzón Zuleta Abogados S.A., and our opinion is subject to the same assumptions, qualifications and limitations with respect to such matters as are contained in such opinion of Gómez-Pinzón Zuleta Abogados S.A.

Also, we have relied as to certain matters on factual information obtained from public officials, officers of the Bank and other sources believed by us to be responsible, and we have assumed that the Indenture has been duly authorized, executed and delivered by the Trustee thereunder, that the Notes conform to the specimens thereof examined by us, that the Trustee’s certificates of authentication of the Notes have been manually signed by one of the Trustee’s authorized officers, and that the signatures on all documents examined by us are genuine, assumptions that we have not independently verified.

We hereby consent to the filing of this opinion on a Form 6-K to be incorporated by reference in the Bank’s Registration Statement on Form F-3 (File No. 333-168077) as Exhibit 5.8 thereto and to the reference to us under the heading “Validity of the Securities” in the Prospectus that is a part thereof and under the heading “Validity of the Notes” in the Prospectus Supplement dated September 4, 2012, relating to the offering of the Notes. In giving such consent, we do not thereby admit that we are in the category of persons whose consent is required under Section 7 of the Act.

Very truly yours,

/s/ SULLIVAN & CROMWELL LLP