Norton Rose Fulbright US LLP

98 San Jacinto Boulevard, Suite 1100

Austin, Texas 78701-4255

United States

Tel +1 512 474 5201

Fax +1 512 536 4598

nortonrosefulbright.com

Exhibit 5.1

September 22, 2017

Veritex Holdings, Inc.

8214 Westchester Drive, Suite 400

Dallas, Texas 75225

Ladies and Gentlemen:

We have acted as special counsel to Veritex Holdings, Inc., a Texas corporation (the “Company”), in connection with the Registration Statement on Form S-4 (the “Registration Statement”), to be filed with the Securities and Exchange Commission (the “SEC”) under the Securities Act of 1933, as amended (the “Securities Act”), on the date hereof, relating to the registration of 1,631,397 shares (the “Shares”) of the Company’s common stock, par value $0.01 per share. The Shares are proposed to be offered to the shareholders of Liberty Bancshares, Inc., a Texas corporation (“Liberty”) pursuant to an Agreement and Plan of Reorganization, dated as of August 1, 2017 (the “Merger Agreement”), by and among the Company, Freedom Merger Sub, Inc., a Texas corporation (“Merger Sub”) and Liberty, pursuant to which Merger Sub will merge with and into Liberty, with Liberty continuing as the surviving corporation and a wholly-owned subsidiary of the Company (the “Merger”). This opinion letter is delivered in accordance with the requirements of Item 601(b)(5) of Regulation S-K under the Securities Act.

In connection with the opinion expressed herein, we have examined originals, or copies certified to our satisfaction, of the following documents: (i) the Second Amended and Restated Certificate of Formation of the Company, as amended; (ii) the Third Amended and Restated Bylaws of the Company, as amended; (iii) the Registration Statement (but not, except as stated otherwise herein, the other Exhibits to the Registration Statement); (iv) the Merger Agreement; (v) relevant resolutions of the board of directors of the Company; and (vi) such other instruments, documents and records as we have deemed necessary, relevant or appropriate for the purposes hereof. We have also reviewed such questions of law as we have deemed necessary or appropriate.

In all such examinations we have assumed the genuineness of all signatures, the authenticity of all documents, certificates and records submitted to us as originals, the conformity to original documents, certificates and records of all documents, certificates and records submitted to us as copies, and the truthfulness of all statements of fact contained therein. We also have assumed, with respect to all parties to agreements or instruments relevant hereto, other than the Company, that such parties had the requisite power and authority (corporate or other) to execute, deliver and perform such agreements or instruments, that such agreements or instruments have been duly authorized by all requisite action (corporate or otherwise), that such agreements or instruments have been executed and delivered by such parties and that such agreements and instruments are the valid, binding and enforceable obligations of such parties. As to various matters of fact relevant to the opinion hereinafter expressed, we have relied upon, and have assumed the accuracy of, certificates and oral or written statements and other information of or from public officials, officers and representatives of the Company and others.

For purposes of this opinion, we have assumed that, prior to the issuance of any Shares, (i) the Registration Statement, including all amendments, will have become effective under the Securities Act and (ii) the Merger will have become effective.

Based on the foregoing, and subject to the limitations, assumptions and qualifications set forth herein, we are of the opinion that the Shares will be validly issued, fully paid and non-assessable.

Veritex Holdings, Inc.

September 22, 2017

Page 2

The foregoing opinion is based on and is limited to the corporate laws of the State of Texas, and we render no opinion with respect to the laws of any other jurisdiction.

We hereby consent to the filing of this opinion with the SEC as an exhibit to the Registration Statement and the reference to this firm under the caption “Legal Matters” in the proxy statement/prospectus forming part of the Registration Statement. In giving this consent, we do not thereby admit that we come within the category of person whose consent is required under Section 7 of the Securities Act or the rules and regulations of the SEC promulgated thereunder.

Very truly yours,

/s/ Norton Rose Fulbright US LLP

Norton Rose Fulbright US LLP