Exhibit 23.1

INDEPENDENT REGISTERED PUBLIC ACCOUNTING FIRM’S CONSENT

We consent to the incorporation by reference in the Registration Statements of National Holdings Corporation (the “Company”) on Form S-8, File No. 333-133733, Form S-8, File No. 333-152962 and Form S-8, File No. 333-191253of our report dated December 27, 2013, on our audits of the consolidated financial statements of the Company as of September 30, 2013 and 2012 and for the years ended September 30, 2013 and 2012, which report is included in this Annual Report on Form 10-K.

/s/ RBSM, LLP

New York, NY

December 27, 2013