Exhibit 5.1 November 19, 2020 Veritex Holdings, Inc. 8214 Westchester Drive, Suite 800 Dallas, Texas 75225 Ladies and Gentlemen: We have acted as counsel to Veritex Holdings, Inc., a Texas corporation (the “Company”), in connection with the registration by the Company under the Securities Act of 1933, as amended (the “Act”), of an indeterminate amount of one or more of the following securities, which the Company may issue from time to time: (i) shares of the Company’s common stock, par value $0.01 per share (the “Common Stock”); (ii) shares of the Company’s preferred stock, par value $0.01 per share (the “Preferred Stock”); (iii) one or more series of senior debt securities of the Company (the “Senior Debt Securities”), to be issued pursuant to a senior debt indenture substantially in the form filed as Exhibit 4.9 to the Registration Statement (as defined below) (the “Senior Debt Indenture”); (iv) one or more series of subordinated debt securities of the Company (the “Subordinated Debt Securities,” and, together with the Senior Debt Securities, the “Debt Securities”), to be issued pursuant to the Subordinated Debt Indenture, dated as of October 5, 2020, between the Company and UMB Bank, N.A., as trustee (the “Trustee,” and such indenture, the “Subordinated Debt Indenture” and, together with the Senior Debt Indenture, the “Indentures”); (v) depositary shares, representing an interest in fractional shares or multiple shares of Preferred Stock and evidenced by a depositary receipt (the “Depositary Shares”); (vi) warrants to purchase Common Stock, Preferred Stock, Depositary Shares or Debt Securities (the “Warrants”); (vii) rights to subscribe for and to purchase Common Stock, Preferred Stock or Debt Securities (the “Subscription Rights”); (viii) purchase contracts that will entitle the holder thereof to purchase a specified number of shares of Common Stock, Preferred Stock, Debt Securities or Depositary Shares at a future date (the “Purchase Contracts”); (ix) purchase units, consisting of Purchase Contracts and Debt Securities (the “Purchase Units”); and (x) units comprised of any combination of Common Stock, Preferred Stock, Senior Debt Securities, Subordinated Debt Securities, Depositary Shares, Warrants, Subscription Rights, Purchase Contracts or Purchase Units (the “Units” and, together with the Senior Debt Securities, Subordinated Debt Securities, Depositary Shares, Warrants, Subscription Rights, Purchase Contracts and Purchase Units, the “Covered Securities”), pursuant to the Company’s registration statement on Form S-3 filed with the United States Securities and Exchange Commission (the “Commission”) on the date hereof (the “Registration Statement”). We have reviewed (i) the Registration Statement, including the form of prospectus included therein, (ii) the form of Senior Debt Indenture filed as Exhibit 4.9 to the Registration Statement and the Subordinated Debt Indenture, (iii) certain resolutions adopted by the Company’s Board of Directors and (iv) such other 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

Veritex Holdings, Inc. November 19, 2020 Page 2 are authentic and that all copies of documents submitted to us conform to the originals, and the truthfulness of all statements of fact contained therein. We have assumed that, at the time of the issuance, sale and delivery of Covered Securities: (i) the execution, delivery and performance by the Company of the Senior Debt Indenture and any applicable supplemental indenture to such indenture or to the Subordinated Debt Indenture, and any deposit agreement, warrant agreement, subscription agreement or subscription rights certificate, purchase contract agreement, purchase unit agreement and unit agreement (collectively with the Subordinated Debt Indenture, the “ Opinion Documents ”), as applicable, and all actions necessary for the issuance of the applicable Covered Securities, and the form and terms thereof, will comply with all requirements and restrictions, if any, applicable to the Company, whether imposed by any agreement or instrument to which the Company is a party or by which it is bound or any court or other governmental or regulatory body having jurisdiction over the Company; (ii) the Company will have duly authorized the execution and delivery of any such Opinion Document and the issuance of any such Covered Securities and such authorizations will not have been modified or rescinded, and there will not have occurred any change in law affecting the validity, legally binding character or enforceability thereof, and (iii) an appropriate prospectus supplement which describes the Covered Securities offered thereby will have been prepared, delivered and filed with the Commission in compliance with the Act and the applicable rules and regulations thereunder. We have also assumed that the Covered Securities will be offered and sold in compliance with applicable federal and state securities laws and in the manner stated in the Registration Statement and the appropriate prospectus supplement. We have assumed further that the Opinion Documents will be governed by and construed in accordance with the laws of the State of New York. We have assumed that the Trustee has duly authorized, executed and delivered the Subordinated Debt Indenture. With respect to any Opinion Document executed or to be executed by any party other than the Company, we have assumed that such party has, or will have, duly authorized, executed and delivered the Opinion Documents to which it is a party and that each such Opinion Document is, or will be, the valid and binding obligation of such party, enforceable against it in accordance with its terms. We have assumed further that the Company is duly organized, validly existing and in good standing under the laws of the State of Texas and has all requisite power, authority and legal right to execute, deliver and perform its obligations under the Covered Securities and the Opinion Documents. With respect to all matters of Texas law, we note that you are relying on an opinion of D. Woodard Glenn, P.C., dated as of the date hereof, which opinion is filed as Exhibit 5.2 to the Registration Statement. 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 on the foregoing and subject to the qualifications set forth herein, we are of the opinion that, when, as and if:

Veritex Holdings, Inc. November 19, 2020 Page 3 1. With respect to any series of Debt Securities: (i) the Registration Statement and any required post-effective amendments thereto all have become effective under the Act and all prospectus supplements required by applicable law have been delivered and filed as required by such laws; (ii) with respect to any series of Senior Debt Securities, (a) the Company has duly authorized the execution, delivery and performance of the Senior Debt Indenture and any necessary indenture supplement thereto and has duly authorized the form, terms, execution and delivery of such Senior Debt Securities, and (b) the Senior Debt Indenture and any necessary supplemental indenture thereto have been duly authorized, executed and delivered by the Company and the Trustee and the Senior Debt Indenture has been qualified under the Trust Indenture Act of 1939, as amended; (iii) with respect to any series of Subordinated Debt Securities, (a) the Company has duly authorized the execution, delivery and performance of any necessary indenture supplement to the Subordinated Debt Indenture and has duly authorized the form, terms, execution and delivery of such Subordinated Debt Securities, and (b) any necessary supplemental indenture has been duly authorized, executed and delivered by the Company and the Trustee; (iv) any legally required consents, approvals, authorizations and other orders of the Commission and any other regulatory authorities have been obtained; and (v) such Debt Securities have been duly executed by the Company and authenticated by the Trustee in accordance with the Indentures, or any applicable indenture supplement, and have been duly issued and delivered against payment therefor in accordance with such corporate action and applicable law and as contemplated in the Registration Statement and the prospectus supplement setting forth the terms of the Debt Securities and the plan of distribution, then, upon the happening of such events, such Debt Securities (including any Debt Securities to be issued by the Company upon the conversion or exercise of other Covered Securities issued by the Company pursuant to the Registration Statement) will constitute the valid and binding obligations of the Company, enforceable against the Company in accordance with their 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. 2. With respect to the Depositary Shares: (i) the Registration Statement and any required post-effective amendments thereto all have become effective under the Act and all prospectus supplements required by applicable law have been delivered and filed as required by such laws; (ii) all necessary corporate action has been taken by the Company to authorize, execute and deliver a deposit agreement and to authorize the form, terms, execution and delivery of any Depositary Shares and to fix or otherwise determine the consideration to be received for the Depositary Shares and the terms of the offer and sale thereof; (iii) any legally required consents, approvals, authorizations and other orders of the Commission and any other regulatory authorities have been obtained; (iv) any shares of Preferred Stock underlying the Depositary Shares have been duly and validly authorized and reserved for issuance and sale; (v) the deposit agreement with respect to the Depositary Shares has been duly authorized, executed and delivered by the Company and the deposit agent; and (vi) the depositary receipts evidencing the Depositary Shares have been duly executed and delivered by the depositary against payment therefor in accordance with the applicable deposit agreement, and in accordance with such corporate action and applicable law and as contemplated in the Registration Statement and the prospectus supplement setting forth the terms of the Depositary Shares and the plan of distribution, then, upon the happening of such

Veritex Holdings, Inc. November 19, 2020 Page 4 events, the Depositary Shares will be legally issued and will entitle the holders thereof to the rights specified in the deposit agreement. 3. With respect to the Warrants: (i) the Registration Statement and any required post- effective amendments thereto all have become effective under the Act and all prospectus supplements required by applicable law have been delivered and filed as required by such laws; (ii) all necessary corporate action has been taken by the Company to authorize, execute and deliver a warrant agreement and to authorize the form, terms, execution and delivery of any Warrants and to fix or otherwise determine the consideration to be received for the Warrants and the terms of the offer and sale thereof; (iii) any legally required consents, approvals, authorizations and other orders of the Commission and any other regulatory authorities have been obtained; (iv) any shares of Common Stock or Preferred Stock or any Depositary Shares issuable or any Debt Securities purchasable upon exercise of such Warrants, as applicable, have been duly and validly authorized and, with respect to shares of Common Stock or Preferred Stock, reserved for issuance and sale; and (v) the warrant agreement with respect to the Warrants has been duly authorized, executed and delivered by the Company and the warrant agent, and the Warrants have been duly executed and delivered by the Company against payment therefor in accordance with any applicable warrant agreement, and in accordance with such corporate action and applicable law and as contemplated in the Registration Statement and the prospectus supplement setting forth the terms of the Warrants and the plan of distribution, then, upon the happening of such events, the Warrants will constitute the valid and binding obligations of the Company, enforceable against the Company in accordance with their 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. 4. With respect to the Subscription Rights: (i) the Registration Statement and any required post-effective amendments thereto all have become effective under the Act and all prospectus supplements required by applicable law have been delivered and filed as required by such laws; (ii) all necessary corporate action has been taken by the Company to authorize, execute and deliver a subscription agreement or subscription rights certificate to the rights agent and to authorize the form, terms, execution and delivery of the Subscription Rights and to fix or otherwise determine the consideration to be received for the Subscription Rights and the terms of the offer and sale thereof; (iii) any legally required consents, approvals, authorizations and other orders of the Commission and any other regulatory authorities have been obtained; (iv) any shares of Common Stock or Preferred Stock issuable or any Debt Securities purchasable upon exercise of such Subscription Rights, as applicable, have been duly and validly authorized and, with respect to shares of Common Stock or Preferred Stock, reserved for issuance and sale; and (v) the subscription agreement or subscription rights certificate with respect to the Subscription Rights has been duly authorized, executed and delivered by the Company and the rights agent, and the Subscription Rights have been duly executed and delivered by the Company against payment therefor in accordance with any applicable subscription agreement or subscription rights certificate, and in accordance with such corporate action and applicable law and as contemplated in the Registration Statement and the prospectus supplement setting forth the terms of the Subscription Rights and the plan of distribution, then, upon the happening of such events, the

Veritex Holdings, Inc. November 19, 2020 Page 5 Subscription Rights will constitute the valid and binding obligations of the Company, enforceable against the Company in accordance with their 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. 5. With respect to the Purchase Contracts and Purchase Units: (i) the Registration Statement and any required post-effective amendments thereto all have become effective under the Act and all prospectus supplements required by applicable law have been delivered and filed as required by such laws; (ii) all necessary corporate action has been taken by the Company to authorize, execute and deliver a purchase contract agreement and/or a purchase unit agreement, as applicable, and to authorize the form, terms, execution and delivery of any Purchase Contracts or Purchase Units, as applicable, and to fix or otherwise determine the consideration to be received for the Purchase Contracts or Purchase Units, as applicable, and the terms of the offer and sale thereof; (iii) any legally required consents, approvals, authorizations and other orders of the Commission and any other regulatory authorities have been obtained; (iv) any shares of Common Stock or Preferred Stock or any Depositary Shares issuable or any Debt Securities purchasable pursuant to such Purchase Contracts or Purchase Units, as applicable, have been duly and validly authorized and, with respect to shares of Common Stock or Preferred Stock, reserved for issuance and sale; and (v) the purchase contract agreement with respect to the Purchase Contracts or purchase unit agreement with respect to the Purchase Units, as applicable, has been duly authorized, executed and delivered by the Company and any other party thereto, and the Purchase Contracts or Purchase Units, as applicable, have been duly executed and delivered by the Company against payment therefor in accordance with any applicable purchase contract agreement or purchase unit agreement, and in accordance with such corporate action and applicable law and as contemplated in the Registration Statement and the prospectus supplement setting forth the terms of the Purchase Contracts or Purchase Units, as applicable, and the plan of distribution, then, upon the happening of such events, the Purchase Contracts or Purchase Units, as applicable, will constitute the valid and binding obligations of the Company, enforceable against the Company in accordance with their 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. 6. With respect to the Units: (i) the Registration Statement and any required post- effective amendments thereto all have become effective under the Act and all prospectus supplements required by applicable law have been delivered and filed as required by such laws; (ii) all necessary corporate action has been taken by the Company to authorize, execute and deliver a unit agreement and to authorize the form, terms, execution and delivery of the Units, the shares of Common Stock or Preferred Stock or other Covered Securities underlying the Units, and the terms of the offer and sale thereof; (iii) any legally required consents, approvals, authorizations and other orders of the Commission and any other regulatory authorities have been obtained; (iv) any shares of Common Stock or Preferred Stock or any Debt Securities, Depositary Shares, Warrants, Subscription Rights, Purchase Contracts or Purchase Units to be issued pursuant to such Units, have been duly and validly authorized and, with respect to shares of Common Stock or Preferred Stock, reserved for issuance and sale; and (v) the unit agreement with respect to the Units

Veritex Holdings, Inc. November 19, 2020 Page 6 has been duly authorized, executed and delivered by the Company and any other party thereto, and the Units have been duly executed and delivered by the Company against payment therefor in accordance with any applicable unit agreement, and in accordance with such corporate action and applicable law and as contemplated in the Registration Statement and the prospectus supplement setting forth the terms of the Units and the other registered securities underlying the Units and the plan of distribution, then, upon the happening of such events, the Units will constitute the valid and binding obligations of the Company, enforceable against the Company in accordance with their 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. Our opinions above are qualified to the extent that the enforcement of any Covered Securities denominated in a currency other than United States dollars may be limited by requirements that a claim (or a foreign currency judgment in respect of such claim) be converted into United States dollars at a rate of exchange prevailing on a date determined pursuant to applicable law. We express no opinion as to: (i) waivers of defenses, subrogation and related rights, rights to trial by jury, rights to object to venue, or other rights or benefits bestowed by operation of law; (ii) releases or waivers of unmatured claims or rights; (iii) indemnification, contribution, exculpation, or arbitration provisions, or provisions for the non-survival of representations, to the extent they purport to indemnify any party against, or release or limit any party’s liability for, its own breach or failure to comply with statutory obligations, or to the extent such provisions are contrary to public policy; or (iv) provisions for liquidated damages and penalties, penalty interest and interest on interest. 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. 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