Exhibit 5.1

February 27, 2015

National Commerce Corporation

813 Shades Creek Parkway, Suite 100

Birmingham, Alabama 35209

Ladies and Gentlemen:

We have acted as counsel to National Commerce Corporation, a Delaware corporation (the “Company”), in connection with the preparation of a registration statement on Form S-1 (No. 333-201371) (the “Registration Statement”) filed by the Company with the Securities and Exchange Commission (the “Commission”) pursuant to the Securities Act of 1933, as amended (the “Securities Act”). The Registration Statement relates to the registration of (i) the offer and sale by the Company of shares of the Company’s common stock, par value $0.01 per share (the “Common Stock”) (together, with additional shares of the Common Stock to be sold by the Company upon the exercise of the underwriters’ option to purchase additional shares, the “Company Securities”) and (ii) the offer and sale by the selling stockholder identified in the Registration Statement (the “Selling Stockholder”) of shares of Common Stock (the “Secondary Securities”). This opinion is being furnished in accordance with the requirements of Item 16(a) of Form S-1 and Item 601(b)(5)(i) of Regulation S-K, as promulgated by the Commission.

In rendering this opinion letter, we have examined originals or copies of the following documents: (a) the Registration Statement, (b) the Company’s Certificate of Incorporation, as amended, (c) the Company’s Bylaws and (d) relevant resolutions of the board of directors of the Company. In addition, we have reviewed the originals or copies certified or otherwise identified to our satisfaction of all such corporate records of the Company and such other documents, and we have made such investigations of law, as we have deemed appropriate as a basis for the opinions expressed below.

In rendering the opinions expressed below, we have assumed the authenticity of all documents submitted to us as originals and the conformity to the originals of all documents submitted to us as copies. In addition, we have assumed and have not verified the accuracy as to factual matters of each document we have reviewed.

Based upon the foregoing, and subject to the assumptions and qualifications set forth above, we are of the opinion that:

1901 SIXTH AVENUE NORTH, 2400 REGIONS/HARBERT PLAZA, BIRMINGHAM, AL 35203-2618 205.254.1000 FAX 205.254.1999

WWW.MAYNARDCOOPER.COM

National Commerce Corporation

February 27, 2015

Page 2

1. The Company Securities have been duly authorized by all necessary corporate action of the Company and, when issued against payment therefor in the manner contemplated by the Registration Statement, will be validly issued by the Company and fully paid and nonassessable.

2. The Secondary Securities have been duly authorized by all necessary corporate action of the Company and are validly issued by the Company and are fully paid and nonassessable.

The foregoing opinions are limited to the General Corporation Law of the State of Delaware, and 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.

We hereby consent to the filing of this opinion letter as Exhibit 5.1 to the Registration Statement and to the use of our name under the caption “Legal Matters” in the prospectus included therein. In giving such consent, we do not admit 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 promulgated thereunder.

Very truly yours,

/s/ Maynard, Cooper & Gale, P.C.