Exhibit 5.1

[LETTERHEAD OF WALLER LANSDEN DORTCH & DAVIS, LLP]

March 23, 2016

BancorpSouth, Inc.

One Mississippi Plaza

201 South Spring Street

Tupelo, Mississippi 38804

Ladies and Gentlemen:

We have acted as counsel to BancorpSouth, Inc., a Mississippi corporation (the “Company”), in connection with a registration statement on Form S-3 (the “Registration Statement”) filed by the Company with the United States Securities and Exchange Commission (“SEC”) under the Securities Act of 1933, as amended (the “Securities Act”), relating to the registration of one or more series of the following securities having an aggregate initial public offering price of up to $675,000,000 (the “Securities”): (i) shares of common stock, $2.50 par value per share, of the Company (the “Common Shares”); (ii) shares of preferred stock, $0.01 par value per share, of the Company (the “Preferred Shares”); (iii) senior debt securities of the Company (the “Senior Debt Securities”); (iv) subordinated debt securities of the Company (the “Subordinated Debt Securities” and, together with the Senior Debt Securities, the “Debt Securities”); (v) warrants to purchase Common Shares, Preferred Shares or Debt Securities (the “Warrants”); (vi) depositary shares representing fractional interests in the Preferred Shares (the “Depositary Shares”); (vii) rights to purchase Common Shares or Preferred Shares (the “Rights”); (viii) purchase contracts representing contractual obligations to purchase or sell Common Shares, Preferred Shares, Debt Securities, Warrants, Depositary Shares or Units (the “Purchase Contracts”); and (ix) units, comprised of any combination of the foregoing securities, which may be separable from one another (the “Units”). The Securities may be offered and sold by the Company from time to time on a delayed or continuous basis as set forth in the prospectus which forms a part of the Registration Statement (the “Prospectus”) and as will be set forth in one or more supplements to the Prospectus (each, a “Prospectus Supplement”).

This opinion letter is furnished to you at your request to enable you to fulfill the requirements of Item 601(b)(5) of Regulation S-K, 17 C.F.R. § 229.601(b)(5), in connection with the Registration Statement.

For purposes of this opinion letter, we have assumed that: (i) the issuance, sale, amount and terms of any Securities to be offered from time to time on a delayed or continuous basis, and any related definitive purchase agreement, underwriting agreement or other similar agreement, Senior Debt Securities Indenture, Subordinated Debt Securities Indenture, Warrant Agreement, Deposit Agreement, Rights Agreement, Purchase Contract Agreement or Unit Agreement, will have been duly authorized and established by proper action of the board of directors of the Company or a duly authorized committee of such board (“Board Action”), consistent with the procedures and terms described in the Registration Statement and in accordance with the Company’s Restated Articles of Incorporation, as amended (the “Articles”), the Company’s Bylaws, as amended and restated, and the Mississippi Business Corporation Act, as amended (“MBCA”), in a manner that does not violate any law, government or court-imposed order or restriction or agreement or instrument then binding on the Company, or otherwise impair the legal or binding nature of the obligations represented by the applicable Securities; (ii) such Board Action shall not have been modified or rescinded; (iii) at the time of offer, issuance and sale of any Securities, the Registration Statement will have been declared effective, and will then be in effect, under the Securities Act; (iv) no stop order suspending the effectiveness of the Registration Statement will have been issued and remain in effect; (v) a Prospectus Supplement with respect to any such Securities shall have been filed with the SEC in compliance with the Securities Act; (vi) prior to any issuance of Preferred Shares or Depositary Shares, articles of amendment to the Articles that have been duly approved by Board Action and by the shareholders of the Company, as applicable, shall be filed for recordation with the Secretary of State of the State of Mississippi; (vii) any Senior Debt Securities will be issued pursuant to a “Senior Debt Securities Indenture,” the form of which is filed as Exhibit 4.1 to the Registration Statement, as supplemented by one or more supplemental indentures, and the Senior Debt Securities Indenture will be qualified under the Trust Indenture Act of 1939, as amended (the “Trust Act”); (viii) any Subordinated Debt Securities will

be issued pursuant to a “Subordinated Debt Securities Indenture,” the form of which is filed as Exhibit 4.2 to the Registration Statement, as supplemented by one or more supplemental indentures, and the Subordinated Debt Securities Indenture will be qualified under the Trust Act; (ix) any Warrants will be issued pursuant to a “Warrant Agreement,” the form of which will be filed by amendment to the Registration Statement or as an exhibit to a document to be incorporated therein by reference, that will be between the Company and a financial institution identified therein as a warrant agent; (x) any Depositary Shares will be issued pursuant to a “Deposit Agreement,” the form of which will be filed by amendment to the Registration Statement or as an exhibit to a document to be incorporated therein by reference, that will be between the Company and the financial institution identified therein as a depositary; (xi) any Rights will be issued pursuant to a “Rights Agreement,” the form of which will be filed by amendment to the Registration Statement or as an exhibit to a document to be incorporated therein by reference, that will be between the Company and a financial institution identified therein as a rights agent, (xii) any Purchase Contracts will be issued pursuant to a “Purchase Contract Agreement,” the form of which will be filed by amendment to the Registration Statement or as an exhibit to a document to be incorporated therein by reference, that will be between the Company and a financial institution identified therein as a purchase contract agent; (xiii) any Units will be issued pursuant to a “Unit Agreement,” the form of which will be filed by amendment to the Registration Statement or as an exhibit to a document to be incorporated therein by reference, that will be between the Company and a financial institution identified therein as a unit agent; (xiv) if being sold, the Securities will be delivered against payment of adequate consideration therefor (in excess of the par value in the case of Common Shares and Preferred Shares) and in accordance with the terms of the applicable Board Action authorizing such sale and any applicable definitive purchase agreement, underwriting agreement or other similar agreement, Senior Debt Securities Indenture, Subordinated Debt Securities Indenture, Warrant Agreement, Deposit Agreement, Rights Agreement, Purchase Contract Agreement or Unit Agreement and as contemplated by the Registration Statement and/or the applicable Prospectus Supplement; (xv) the laws of the State of New York will be the governing law under any Senior Debt Securities Indenture, Subordinated Debt Securities Indenture, Deposit Agreement, Warrant Agreement, Rights Agreement, Purchase Contract Agreement and Unit Agreement; and (xvi) the Company will remain a validly existing corporation in good standing under the laws of the State of Mississippi.

For purposes of this opinion letter, we have examined copies of such agreements, instruments and documents as we have deemed an appropriate basis on which to render the opinions hereinafter expressed. In our examination of the aforesaid documents, we have assumed the genuineness of all signatures, the legal capacity of all natural persons, the accuracy and completeness of all documents submitted to us, the authenticity of all original documents, and the conformity to authentic original documents of all documents submitted to us as copies (including telecopies, .pdf copies and other imaged copies). As to all matters of fact, we have relied on the representations and statements of fact made in the documents so reviewed, and we have not independently established the facts so relied on. This opinion letter is given, and all statements herein are made, in the context of the foregoing.

In rendering the following opinions, we state that we express no opinion as to the laws, statutes, ordinances, rules, or regulations of any jurisdiction other than the States of Mississippi and New York (and in particular, we express no opinion as to any effect that such other laws, statutes, ordinances, rules, or regulations may have on the opinions expressed herein). In particular, this opinion letter is based as to matters of law solely upon the applicable provisions of the following, in each case as in effect on the date of this opinion letter: (i) as to the opinions given in paragraphs (1) and (2), the MBCA, and (ii) as to the opinions given in paragraphs (3), (4), (5), (6), (7), (8) and (9), the MBCA and the applicable contract laws of the State of New York (but not including any laws, statutes, ordinances, administrative decisions, rules or regulations of any political subdivision below the state level).

All opinions expressed are as of the date hereof except where expressly stated otherwise.

The opinions expressed in paragraphs (3), (4), (5), (6), (7), (8) and (9) with respect to the valid and binding nature of obligations may be limited by (i) bankruptcy, insolvency, reorganization, fraudulent transfer, moratorium and other similar laws now or hereafter in effect relating to or affecting creditors’ rights generally and (ii) general principles of equity (regardless of whether considered in a proceeding at law or in equity), including, but not limited to, the following concepts: (a) principles governing the availability of specific performance, injunctive relief or other traditional equitable remedies; (b) principles affording traditional equitable defenses (e.g., waiver, laches and estoppel); (c) good faith and fair dealing; (d) reasonableness; (e) materiality of the breach; (f) impracticability or impossibility of performance; (g) the effect of obstruction or failure to perform or otherwise act in accordance with any agreement by any person other than the Company; and (h) unconscionability.

Based upon, subject to and limited by the foregoing, we are of the opinion that, as of the date of this opinion letter:

1. The Common Shares (including any Common Shares duly issued upon the exchange or conversion of Preferred Shares or Debt Securities that are exchangeable for or convertible into Common Shares or upon the exercise of Warrants, Rights, Purchase Contracts or Units and receipt by the Company of any additional consideration payable upon such conversion, exchange or exercise), upon due execution and delivery on behalf of the Company of certificates therefor, including global certificates, or the entry of the issuance thereof in the books and records of the Company, as the case may be, will be validly issued, fully paid and non-assessable.

2. The Preferred Shares (including any Preferred Shares represented by Depositary Shares or that are duly issued upon the exercise of Warrants, Rights, Purchase Contracts or Units and receipt by the Company of any additional consideration payable upon such exercise), upon due execution and delivery on behalf of the Company of certificates therefor, including global certificates, or the entry of the issuance thereof in the books and records of the Company, as the case may be, will be validly issued, fully paid and non-assessable.

3. The Senior Debt Securities (including any Senior Debt Securities duly issued upon the exercise of Warrants, Purchase Contracts or Units), upon due execution and delivery of a Senior Debt Securities Indenture, including any supplemental indenture, on behalf of the Company and the trustee named therein, upon due authentication of such Senior Debt Securities by such trustee, and upon due execution, issuance and delivery of the Senior Debt Securities in accordance with the Senior Debt Securities Indenture, including any supplemental indenture, will constitute valid and binding obligations of the Company.

4. The Subordinated Debt Securities (including any Subordinated Debt Securities duly issued upon the exercise of Warrants, Purchase Contracts or Units), upon due execution and delivery of a Subordinated Debt Securities Indenture, including any supplemental indenture, on behalf of the Company and the trustee named therein, upon due authentication of such Subordinated Debt Securities by such trustee, and upon due execution, issuance and delivery of the Subordinated Debt Securities in accordance with the Subordinated Debt Securities Indenture, will constitute valid and binding obligations of the Company.

5. The Warrants, upon due execution and delivery of a Warrant Agreement on behalf of the Company and the warrant agent named therein, upon due authentication of the Warrants and Warrant certificates by such warrant agent, and upon due execution, issuance and delivery of the Warrants and Warrant certificates in accordance with the Warrant Agreement, will constitute valid and binding obligations of the Company.

6. The depositary receipts evidencing the Depositary Shares, upon due countersignature thereof and issuance against a deposit of duly authorized and validly issued Preferred Shares in accordance with the Deposit Agreement, will be validly issued and entitle the holders thereof to the rights specified in such depositary receipts and Deposit Agreement.

7. The Rights, upon due execution and delivery of a Rights Agreement on behalf of the Company and the rights agent named therein, upon due authentication of the rights certificates by such rights agent, and upon due execution, issuance and delivery of one or more rights certificates in accordance with the Rights Agreement, will constitute valid and binding obligations of the Company.

8. The Purchase Contracts, upon due execution and delivery of a Purchase Contract Agreement on behalf of the Company and the purchase contract agent named therein, upon due authentication of the Purchase Contracts by such purchase contract agent, and upon due execution, issuance and delivery of the Purchase Contracts in accordance with the Purchase Contract Agreement, will constitute valid and binding obligations of the Company.

9. The Units, upon due execution and delivery of a Unit Agreement on behalf of the Company and the unit agent named therein, upon due authentication of the Units and Unit certificates by such unit agent, and upon due execution, issuance and delivery of the Units and Unit certificates in accordance with the Unit Agreement, will constitute valid and binding obligations of the Company.

To the extent that the obligations of the Company under any agreement (including, without limitation, any Senior Debt Securities Indenture, Subordinated Debt Securities Indenture, Warrant Agreement, Deposit Agreement, Rights Agreement, Purchase Contract Agreement or Unit Agreement) may be dependent upon such matters, we assume for purposes of this opinion that: (i) the other party or parties to such agreement 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 is duly qualified to engage in the activities contemplated by the agreement, as applicable; (iii) such agreement has been duly authorized, executed and delivered by the other party or parties to such agreement, as applicable, and constitutes the valid and binding obligation of the other party or parties to such agreement, as applicable, enforceable against the other party or parties to such agreement, as applicable, in accordance with its terms; (iv) the other party or parties to such agreement is in compliance, with respect to any actions the other party to such agreement may take under such agreement, as applicable, with all applicable laws and regulations; (v) the other party or parties to such agreement has the requisite organizational and legal power and authority to perform its obligations under such agreement, as applicable; and (vi) such agreement (other than any Senior Debt Securities Indenture or Subordinated Debt Securities Indenture) does not violate any applicable law, conflict with any applicable governmental authority or any other agreement or instrument to which any party to such agreement is bound.

We assume no obligation to advise you of any changes in the foregoing subsequent to the delivery of this opinion letter. This opinion letter has been prepared for use in connection with the filing of the Registration Statement on the date of this opinion letter.

We hereby consent to the filing of this opinion letter as an exhibit to the Registration Statement and further consent to the reference to this firm under the caption “Validity of Securities” in the prospectus constituting a part of the Registration Statement. 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 Securities Act.

Very truly yours,

/s/ WALLER LANSDEN DORTCH & DAVIS, LLP