Exhibit 23.1

Consent of Independent Registered Public Accounting Firm

We consent to the inclusion in this Registration Statement on Form S-4 of Virginia National Bankshares Corporation of our report dated March 20, 2013, relating to our audits of the consolidated balance sheets of Virginia National Bank and subsidiary as of December 31, 2012 and 2011, and the related consolidated statements of income, comprehensive income, shareholders’ equity, and cash flows for the years then ended appearing in the Proxy Statement/Prospectus, which is part of this Registration Statement. We further consent to the reference to our Firm under the caption “Experts” in the Registration Statement.

Winchester, Virginia

April 12, 2013