EXHIBIT 5.1

May 7, 2015

Avenue Financial Holdings Inc.

111 10^th Avenue South, Suite 400

Nashville, TN 37203

Re: Avenue Financial Holdings, Inc. Registration Statement on Form S-1

Ladies and Gentlemen:

We have acted as counsel to Avenue Financial Holdings, Inc., a Tennessee corporation (the “Company”), in connection with the Registration Statement on Form S-1 (the “Registration Statement”) being filed by the Company with the Securities and Exchange Commission pursuant to the Securities Act of 1933, as amended (the “Act”), relating to the registration for resale by certain selling securityholders of $20,000,000 aggregate principal amount of the Company’s Fixed/Floating Rate Subordinated Notes due 2024 (the “Subordinated Notes”) issued pursuant to Note Purchase Agreements dated as of December 22, 2014 (the “Note Purchase Agreements”) among the Company and each of the selling securityholders.

In so acting, we have examined, and relied as to matters of fact upon, the originals, or copies certified or otherwise identified to our satisfaction, of the Restated Charter and Amended and Restated By Laws of the Company, the Note Purchase Agreements, the Subordinated Notes, the Registration Statement, including, without limitation, all exhibits thereto, and such other certificates (including certificates of officers of the Company), records, instruments and documents, and have made such other and further investigations, as we have deemed necessary or appropriate to enable us to express the opinion set forth below. In such examination, we have assumed the genuineness of all signatures, the legal capacity of natural persons, the authenticity of all documents submitted to us as originals, the conformity to original documents or all documents submitted to us as certificate or photostatic copies, and the authenticity of the originals of such latter documents. We have also made such investigations of law as we have deemed necessary or appropriate to form a basis for the opinion expressed herein.

Based upon and subject to the foregoing and the additional qualifications set forth below, we are of the opinion that the Subordinated Notes constitute the legal, valid and binding obligations of the Company enforceable against the Company in accordance with their terms, subject to applicable bankruptcy, insolvency, fraudulent conveyance, reorganization, moratorium and similar laws affecting creditors’ rights and remedies generally, and subject, as to enforceability, to general principles of equity, including principles of commercial reasonableness, good faith and fair dealing (regardless of whether enforcement is sought in a proceeding at law or in equity).

This opinion is limited to the corporate laws of the State of Tennessee in effect on the date hereof and no opinion is expressed as to the laws of any other jurisdiction.

We hereby consent to the filing of this opinion as an exhibit to the Registration Statement and to the reference to our firm under the heading “Legal Matters” in the prospectus that is a part of the Registration Statement. In giving the foregoing consent, we do not admit that we are in the category of persons whose consent is required under Section 7 of the Act, or the rules and regulations of the Securities and Exchange Commission promulgated thereunder.

Very truly yours,

/s/ Bradley Arant Boult Cummings LLP