Exhibit 5.1

May 19, 2016

National Commerce Corporation

813 Shades Creek Parkway, Suite 100

Birmingham, Alabama 35209

Re: Subordinated Notes Offering Pursuant to Registration Statement on Form S-3

Ladies and Gentlemen:

We have acted as counsel to National Commerce Corporation, a Delaware corporation (the “Company”), in connection with the public offering of $25,000,000 aggregate principal amount of the Company’s 6.0% Fixed-to-Floating Rate Subordinated Notes due June 1, 2026 (the “Notes”) pursuant to an Underwriting Agreement, dated May 19, 2016 (the “Underwriting Agreement”), between the Company, as issuer, and Keefe, Bruyette & Woods, Inc., as underwriters. The Notes will be issued pursuant to an Indenture dated as of May 19, 2016 (the “Base Indenture”), between the Company and The Bank of New York Mellon Trust Company, N.A., as trustee (the “Trustee”), as supplemented by the First Supplemental Indenture between the Company and the Trustee dated as of May 19, 2016 (the Base Indenture, together with the First Supplemental Indenture, the “Indenture”).

This opinion letter is being furnished in accordance with the requirements of Item 601(b)(5) of Regulation S-K under the Securities Act of 1933, as amended (the “Securities Act”).

In connection with this opinion letter, we have examined and relied on originals, or copies certified or otherwise identified to our satisfaction, of (i) the Company’s Registration Statement on Form S-3 (File No. 333-210687) filed with the Securities and Exchange Commission (the “Commission”) on April 11, 2016, as amended on May 2, 2016 (as so amended, the “Registration Statement”), which Registration Statement was declared effective by the Commission on May 9, 2016; (ii) the base prospectus dated April 11, 2016 relating to the Registration Statement (the “Base Prospectus”) and the prospectus supplement dated May 16, 2016 relating to the Notes (the “Prospectus Supplement”); (iii) the Underwriting Agreement; (iv) the Indenture; (v) the form of Notes; (vi) certain resolutions of the Board of Directors of the Company adopted as of May 12, 2016 and of the Pricing Committee of the Board of Directors of the Company duly adopted on May 16, 2016 relating to the Notes; (vii) the Certificate of Incorporation of the Company, as amended and currently in effect; (viii) the Bylaws of the Company as currently in effect; (ix) a Certificate of Good Standing issued by the Secretary of State of the State of Delaware on May 17, 2016 with respect to the Company; and (x) such other records, documents, certificates and other instruments and such matters of law as in our judgment are necessary or appropriate to enable us to render the opinion expressed below.

In our examination, we have assumed without independent investigation or inquiry the legal capacity of all natural persons executing documents, the genuineness of all signatures on original or certified copies, the authenticity of all original or certified copies and the conformity to original or certified documents of all copies submitted to us as conformed or reproduction copies. In making our examination of executed documents or documents to be executed, we have assumed that the parties thereto, other than the Company, had or will have the power, corporate or other, to enter into and perform all obligations thereunder and have also assumed the due authorization by all requisite action, corporate or other, and execution and delivery by such parties of such documents, and the validity and binding effect on such parties. We have relied as to factual matters upon, and have assumed the accuracy of, the representations and warranties contained in or made pursuant to the Underwriting Agreement and statements or information of or from public officials and other officers and representatives of the Company and its subsidiaries. We have also assumed that: (i) the Indenture will be a valid and binding obligation of the Trustee; and (ii) the Notes have been duly authenticated by the Trustee.

Based on the foregoing and subject to the assumptions, exceptions, qualifications and limitations set forth herein, we are of the opinion that the Notes, when executed, authenticated and delivered in accordance with the terms of the Indenture, will constitute valid and binding obligations of the Company, enforceable against the Company in accordance with their terms, except as may be limited by applicable bankruptcy, insolvency, reorganization, moratorium, fraudulent conveyance or similar laws of general applicability relating to or affecting the rights and remedies of creditors and by general principles of equity, constitutionality and public policy (whether considered in a proceeding at law or in equity).

Our opinion is limited to the laws of the State of New York and the General Corporation Law of the State of Delaware. We do not express any opinion with respect to the law of any other jurisdiction or to the securities or “blue sky” laws of any jurisdiction. Our opinion is strictly limited to the matters stated in this letter, and no other opinions are to be implied. Without limiting the generality of the foregoing, we specifically express no opinion as to (i) the validity or enforceability of any provisions of the Notes or Indenture relating to indemnification, contribution, exculpation or limitation of liability in connection with liability for the indemnified or exculpated party’s own action or inaction to the extent that the action or inaction involves gross negligence, recklessness, willful misconduct or unlawful conduct, or provisions with respect to indemnification obligations of the Company to the extent that such obligations encompass claims made by the Company or any of its affiliates; (ii) the enforceability of any provision of the Indenture or Notes purporting to waive the right to assert counterclaims or setoff; or (iii) the validity or enforceability of the provisions of the Notes or Indenture purporting to grant or consent to exclusive jurisdiction in any court or to waive objections to venue, personal service of process in connection with any judicial process, or trial by jury.

The opinion set forth herein is made as of the date hereof and is subject to, and may be limited by, future changes in the factual matters set forth herein, and we undertake no duty to advise you of the same. The opinion set forth herein is based on the law in effect (and published or otherwise generally available) on the date hereof, and we assume no obligation to revise or supplement this opinion letter should such law be changed by legislative action, judicial decision or otherwise. In rendering our opinion, we have not considered, and hereby disclaim any opinion as to, the application or impact of any laws, cases, decisions, rules or regulations of any other jurisdiction, court or administrative agency.

We hereby consent to the filing of this opinion letter as an exhibit to the Company’s Current Report on Form 8-K to be filed by the Company with the Commission on the date hereof, the incorporation by reference thereof in the Registration Statement and to the use of our name under the caption “Legal Matters” in the Prospectus Supplement. In giving such consent, we do not thereby concede that we are within the category of persons whose consent is required under Section 7 of the Securities Act or the rules and regulations of the Commission thereunder.

3