QuickLinks -- Click here to rapidly navigate through this document

Exhibit 23.6

Consent of Independent Auditor

        We consent to the incorporation by reference in this Registration Statement on Form S-4 of Veritex Holdings, Inc. of our report dated March 30, 2017, relating to the consolidated financial statements of Sovereign Bancshares, Inc.

        We also consent to the reference to our firm under the heading "Experts" in the proxy statement/prospectus, which is part of this Registration Statement.

/s/ RSM US LLP
Dallas, Texas
August 31, 2018

QuickLinks

Exhibit 23.6

Consent of Independent Auditor