Exhibit 5.1

January 30, 2015

Avenue Financial Holdings Inc.

111 10^th Avenue South, Suite 400

Nashville, TN 37203

Ladies and Gentlemen:

We have acted as counsel for Avenue Financial Holdings, Inc., a Tennessee corporation (the “Company”), in connection with the Registration Statement on Form S-1 (Registration File No. 333-201438) (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 of 2,875,000 shares of common stock, no par value, of the Company (the “Shares”), including (i) 1,543,655 Shares (inclusive of up to 219,390 Shares for an over-allotment option) to be issued and sold by the Company (the “Company Shares”) and (ii) 1,331,345 Shares (inclusive of up to 155,610 Shares for an over-allotment option) to be resold by those entities identified as selling stockholders in the Registration Statement (collectively, the “Selling Stockholders”) (the “Selling Stockholders’ Shares”). This opinion is being filed pursuant to the requirements of Item 601(b)(5) of Regulation S-K under the Act.

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, resolutions adopted by the Board of Directors of the Company dated January 20, 2015 authorizing and approving the issuance of the Company Shares, stock records of the Company and agreements pursuant to which the Selling Stockholders’ Shares were issued to the Selling Stockholders and 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 (i) the Company Shares, when issued, sold, delivered and paid for in the manner described in the Registration Statement, will be legally issued, fully paid and non-assessable and (ii) the Selling Stockholders’ Shares to be sold by the Selling Stockholders pursuant to the Registration Statement are legally issued, fully paid and non-assessable.

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.

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.

/s/ Bradley Arant Boult Cummings LLP