Exhibit 5.1

Opinion of Sullivan & Cromwell LLP

August 12, 2020

Cullen/Frost Bankers, Inc.

111 West Houston Street

San Antonio, Texas 78205

Ladies and Gentlemen:

We are acting as counsel to Cullen/Frost Bankers, Inc., a Texas corporation (the “Company”) in connection with the filing of the Company’s registration statement on Form S-3 (the “Registration Statement”) under the Securities Act of 1933 (the “Act”). The Registration Statement registers (i) shares of common stock of the Company, par value $0.01 per share (the “Common Shares”); (ii) shares of preferred stock of the Company, par value $0.01 per share (the “Preferred Shares”); (iii) depositary shares representing Preferred Shares (the “Depositary Shares”); (iv) debt securities, including senior debt securities and subordinated debt securities, of the Company (the “Debt Securities”); and (v) warrants to purchase Common Shares, Preferred Shares or Debt Securities (the “Warrants”). The Depositary Shares, Debt Securities and Warrants are referred to collectively as the “Securities”.

In connection with the filing of the Registration Statement, we, as your 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:

(1)Depositary Shares. When the Registration Statement has become effective under the Act, when the terms of the deposit agreements under which the Depositary Shares are to be issued have been duly established and the deposit agreements have been duly executed and delivered, when the terms of the Depositary Shares and of their issuance and sale have been duly established in conformity with the applicable deposit agreements, when the Preferred Shares represented by the Depositary Shares have been duly authorized and validly issued by the Company and are fully paid and non-assessable and duly delivered to the applicable depositaries and when the depositary receipts evidencing the Depositary Shares have been duly issued against deposit of the Preferred Shares in accordance with the applicable deposit agreements and issued and sold as contemplated by the Registration Statement, and if all the foregoing actions are taken pursuant to authority granted in resolutions duly adopted by the Company’s Board of Directors, or a duly authorized committee thereof, and so as not to violate any applicable law or result in a default under or breach of any agreement or instrument binding upon the Company and so as to comply with any requirement or restriction imposed by any court or governmental body having jurisdiction over the Company, the depositary receipts evidencing the Depositary Shares will be validly issued and will entitle the holders thereof to the rights specified in the Depositary Shares and the applicable deposit agreements, 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.

(2)Debt Securities. When the Registration Statement has become effective under the Act, when an indenture relating to the senior debt securities (the “Senior Debt Indenture”) has been duly authorized, executed and delivered substantially in the form so filed, when the terms of the Debt Securities and of their issuance and sale have been duly established in conformity with the Senior Debt Indenture or the Indenture, dated as of February 15, 2007, relating to the subordinated debt securities, between the Company and The Bank of New York Mellon, formerly known as The Bank of New York (the “Subordinated Debt Indenture” and each of the Senior Debt Indenture and Subordinated Debt Indenture, an “Indenture”), as applicable, so as not to violate any applicable law or result in a default under or breach of any agreement or instrument binding upon the Company and so as to comply with any requirement or restriction imposed by any court or governmental body having jurisdiction over the Company, and when the Debt

Securities have been duly executed and authenticated in accordance with the applicable Indenture and issued and sold as contemplated in the Registration Statement, and if all the foregoing actions are taken pursuant to authority granted in resolutions duly adopted by the Company’s Board of Directors, or a duly authorized committee thereof, the Debt Securities will constitute valid and legally binding obligations of the Company, 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 Debt Securities covered by the opinion in this paragraph include any Debt Securities that may be issued upon exercise of any Warrants that are exercisable for Debt Securities.

(1)Warrants. When the Registration Statement has become effective under the Act, when the terms of the warrant agreement under which the Warrants are to be issued have been duly established and the warrant agreement has been duly authorized, executed and delivered, when the terms of the Warrants and of their issuance and sale have been duly established in conformity with the applicable warrant agreement and when the Warrants have been duly executed and authenticated in accordance with the applicable warrant agreement and issued and sold as contemplated by the Registration Statement, and if all the foregoing actions are taken pursuant to authority granted in resolutions duly adopted by the Company’s Board of Directors, or a duly authorized committee thereof, and so as not to violate any applicable law or result in a default under or breach of any agreement or instrument binding upon the Company and so as to comply with any requirement or restriction imposed by any court or governmental body having jurisdiction over the Company, the Warrants will constitute valid and legally binding obligations of the Company, 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.

We note that, as of the date of this opinion, a judgment for money in an action based on a Security denominated in a foreign currency or currency unit in a Federal or state court in the United States ordinarily would be enforced in the United States only in United States dollars. The date used to determine the rate of conversion of the foreign currency or currency unit in which a particular Security is denominated into United States dollars will depend upon various factors, including which court renders the judgment. Under Section 27 of the New York Judiciary Law, a state court in the State of New York rendering a judgment on such Security would be required to render such judgment in the foreign currency or currency unit in which the Security is denominated, and such judgment would be converted into United States dollars at the exchange rate prevailing on the date of entry of the judgment.

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 purposes of this opinion, we have, with your approval, assumed that (i) the Company has been duly incorporated and is an existing corporation in good standing under the laws of the State of Texas, (ii) each deposit agreement, each applicable Indenture and each warrant agreement has or will be duly authorized, executed and delivered by the Company insofar as Texas law is concerned and (iii) the Securities will be duly authorized, issued and delivered by the Company insofar as Texas law is concerned.

We have relied as to certain factual matters on information obtained from public officials, officers of the Company and other sources believed by us to be responsible, and we have assumed that the Subordinated Debt Indenture has been, and the Senior Debt Indenture will be, duly authorized, executed and delivered by the applicable trustee thereunder, an assumption which we have not independently verified. We have assumed that the governing documents under which the Securities are to be issued will have been duly authorized, executed and delivered by all parties thereto other than the Company and that the signatures on documents examined by us are genuine. We have further assumed that the issuance or delivery by the Company of any securities other than the Securities, or of any other property, upon exercise or otherwise pursuant to the terms of the Securities will be effected pursuant to authority granted in resolutions duly adopted by the Company’s Board of Directors, or a duly authorized committee thereof, so as not to violate any applicable law or result in a default under or breach of any agreement or instrument binding on the Company and so as to comply with any requirement or restriction imposed by any court or governmental body having jurisdiction over the Company. Finally, we have assumed that the authority granted in resolutions duly adopted by the Company’s Board of Directors, or a duly authorized committee thereof, will remain in effect at all relevant times and that no Securities will be issued or other action taken in contravention of any applicable limit established pursuant to such resolutions from time to time. In rendering the foregoing opinion, we are not passing upon, and assume no responsibility for, any disclosure in the Registration Statement or any related prospectus or other offering material regarding the Company or the Securities or their offering and sale.

-2-

We hereby consent to the filing of this opinion as an exhibit to the Registration Statement and to the reference to us under the heading “Validity of the Securities” in the prospectus contained therein. 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

-3-