Exhibit 5.1

[LETTERHEAD OF COVINGTON & BURLING LLP]

December 12, 2008

Ladies and Gentlemen:

We have acted as special counsel to Trustmark Corporation, a Mississippi corporation (the “Company”), in connection with the registration by the Company under the Securities Act of 1933 (the “Act”), on a registration statement on Form S-3 filed with the United States Securities and Exchange Commission (the “Commission”) on or about the date hereof (such registration statement is herein referred to as the “Registration Statement”), of resales from time to time of (a) 215,000 shares of Fixed Rate Cumulative Perpetual Preferred Stock, Series A, no par value, of the Company (the “Preferred Shares”), (b) a warrant dated November 21, 2008 (the “Warrant”) to purchase common stock, no par value, of the Company (the “Common Stock”); and (c) the 1,647,931 shares (as such amount may be adjusted from time to time pursuant to the terms of the Warrant) of Common Stock for which the Warrant may be exercised (the “Warrant Shares,” and, together with the Warrant and the Preferred Shares, the “Securities”).  All of the Securities are being registered on behalf of the selling securityholder named in the Registration Statement.

We have reviewed 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.  We have assumed that all signatures are genuine, that all documents submitted to us as originals are authentic and that all copies of documents submitted to us conform to the originals.

We have assumed that the Company is a corporation duly organized, validly existing and in good standing under the law of the State of Mississippi and has all requisite power, authority and legal right to execute, deliver and perform the Warrant.  We have assumed further that, insofar as the law of the State of Mississippi is concerned, that (i) the Warrant has been duly authorized, executed and delivered, and (ii) the Warrant constitutes the valid and binding obligation of the Company, enforceable against the Company in accordance with its terms.

We have relied as to certain matters on information obtained from public officials, officers of the Company, and other sources believed by us to be responsible.

Based upon the foregoing, we are of the opinion that, insofar as the law of the State of New York and, if and to the extent applicable, the Federal law of the United States of America, are concerned, the Warrant constitutes a valid and binding obligation of the Company, enforceable against the Company in accordance with its terms, subject to bankruptcy, insolvency, fraudulent transfer, reorganization, moratorium and other laws of general applicability relating to or affecting creditors’ rights and to general equity principles.

We are members of the bar of the State of New York.  We do not express any opinion herein on any laws other than the law of the State of New York and the Federal law of the United States of America.

We hereby consent to the filing of this opinion as Exhibit 5.1 to the Registration Statement.  We also hereby consent to the reference to our firm under the heading “Legal Matters” in the prospectus constituting 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 Act.

Very truly yours,

/s/ COVINGTON & BURLING LLP