Exhibit 10.1

EXECUTION VERSION

VOTING AGREEMENT

This VOTING AGREEMENT (this “Agreement”), dated as of March 20, 2014 among Xenith Bankshares, Inc., a Virginia corporation (“Parent”), and each of the undersigned, a list of which is set forth on Exhibit A attached hereto (each, a “Shareholder”).

WHEREAS, in order to induce Parent to enter into an Agreement of Merger, dated as of the date hereof (the “Merger Agreement”), between Colonial Virginia Bank, a Virginia banking corporation (“CVB”), Parent and Xenith Bank, a Virginia banking corporation and a wholly-owned subsidiary of Parent (“Xenith Bank”), Parent has requested each Shareholder, and each Shareholder has agreed, to enter into this Agreement with respect to all shares of common stock, par value $5.00 per share, of CVB that such Shareholder beneficially owns and either (i) holds jointly with another Shareholder, (ii) holds through an investment entity over which such Shareholder has sole or shared control or (iii) with respect to which such Shareholder has sole voting power (with respect to each Shareholder, the “Shares”) (as used herein, the term “Shares” shall mean (A) all securities of CVB (including all shares of CVB capital stock and all options, warrants and other rights to acquire shares of CVB capital stock) owned by a Shareholder as of the date of this Agreement and either (i) held jointly with another Shareholder, (ii) held through an investment entity over which such Shareholder has sole or shared control or (iii) with respect to which such Shareholder has sole voting power, all as indicated on the signature page hereto, and (B) all additional securities of CVB (including all additional shares of CVB capital stock and all additional options, warrants and other rights to acquire shares of CVB capital stock) of which a Shareholder acquires beneficial ownership during the period commencing on the execution and delivery of this Agreement until termination of this Agreement in accordance with Section 5.02 hereof, but excluding in either case any Shares Transferred (as defined below) by a Shareholder to any Person (other than another Shareholder) in accordance with the terms of this Agreement).

NOW, THEREFORE, the parties hereto agree as follows:

ARTICLE 1

GRANT OF PROXY; VOTING AGREEMENT

Section 1.01. Voting Agreement. Each Shareholder hereby agrees to vote or exercise its right to consent with respect to all Shares that such Shareholder is entitled to vote at the time of any vote or action by written consent to approve and adopt the Merger Agreement, the Merger, the Plan of Merger and all agreements related to the Merger and any actions related thereto at any meeting of the shareholders of CVB, and at any adjournment thereof, at which such Merger Agreement, Plan of Merger and other related agreements (or any amended version

thereof), or such other actions, are submitted for the consideration and vote of the shareholders of CVB. Each Shareholder hereby agrees that, for so long as this Agreement is in effect, it will not vote any Shares in favor of, or consent to, and will vote such Shares against and not consent to, the approval of any (i) Acquisition Proposal, (ii) reorganization, recapitalization, liquidation or winding-up of CVB or any other extraordinary transaction involving CVB, other than to vote in favor of, or consent to, the Merger Agreement, the Merger and the Plan of Merger, (iii) corporate action the consummation of which may frustrate the purposes, or prevent or delay the consummation of, the transactions contemplated by the Merger Agreement or (iv) other matter relating to, or in connection with, any of the foregoing matters.

Section 1.02. Irrevocable Proxy. Each Shareholder hereby revokes any and all previous proxies granted with respect to such Shareholder’s Shares. By entering into this Agreement, each Shareholder hereby grants a proxy appointing Parent as such Shareholder’s attorney-in-fact and proxy, with full power of substitution, for and in such Shareholder’s name, to vote, express consent or dissent, or otherwise to utilize such voting power in the manner contemplated by Section 1.01 above as Parent or its proxy or substitute shall, in Parent’s sole discretion, deem proper with respect to such Shareholder’s Shares. The proxy granted by each Shareholder pursuant to this Article 1 is irrevocable and is granted in consideration of Parent entering into this Agreement and the Merger Agreement and incurring certain related fees and expenses. The proxy granted by each Shareholder shall be revoked upon termination of this Agreement in accordance with its terms.

Section 1.03. No Ownership Interest. Except as set forth in Section 1.02, nothing contained in this Agreement shall be deemed to vest in Parent any direct or indirect ownership or incidence of ownership of or with respect to any Shares. All rights, ownership and economic benefits of and relating to the Shares shall remain and belong to the Shareholders, and Parent shall have no authority to manage, direct, superintend, restrict, regulate, govern or administer any of the policies or operations of CVB or exercise any power or authority to direct the Shareholders in the voting of any of the Shares, except as set forth in Section 1.02 or as otherwise expressly provided herein, or the performance of its duties or responsibilities as a shareholder of CVB.

Section 1.04. Other Agreements. Prior to the termination of this Agreement in accordance with Section 5.02 hereof, each of the Shareholders shall not enter into any agreement or understanding with any person to vote or give instructions in any manner inconsistent with this Article 1.

2

ARTICLE 2

REPRESENTATIONS AND WARRANTIES OF THE SHAREHOLDERS

Each Shareholder severally represents and warrants to Parent that:

Section 2.01. Authorization. Such Shareholder has duly executed and delivered this Agreement and the execution, delivery and performance by such Shareholder of this Agreement and the consummation by such Shareholder of the transactions contemplated hereby are within the powers and legal capacity of such Shareholder and have been duly authorized by all necessary action. Assuming due authorization, execution and delivery by Parent, this Agreement is a valid and binding agreement of such Shareholder. If such Shareholder is married and the Shares set forth on the signature page hereto opposite such Shareholder’s name constitute community property under applicable laws, this Agreement has been duly authorized, executed and delivered by, and constitutes the valid and binding agreement of, such Shareholder’s spouse.

Section 2.02. Non-Contravention. The execution, delivery and performance by such Shareholder of this Agreement and the consummation of the transactions contemplated hereby do not and will not (i) violate any law, rule, regulation, judgment, injunction, order or decree applicable to or binding upon the Shareholder, (ii) require any consent or other action by any Person under, constitute a default under, or give rise to any right of termination, cancellation or acceleration or to a loss of any benefit to which such Shareholder is entitled under any provision of any agreement or other instrument binding on such Shareholder or (iii) result in the imposition of any Lien on any asset of such Shareholder.

Section 2.03. Ownership of Shares. Except for the Shares identified as held “jointly with spouse” on the signature page, such Shareholder is the record and beneficial owner of such Shareholder’s Shares, free and clear of any Lien and any other limitation or restriction (including any restriction on the right to vote or otherwise dispose of such Shares). The Shareholders jointly hold the Shares identified as held “jointly with spouse” on the signature page, free and clear of any Lien and any other limitation or restriction (including any restriction on the right to vote or otherwise dispose of such Shares). None of such Shareholder’s Shares is subject to any voting trust or other agreement or arrangement with respect to the voting of such Shares.

Section 2.04. Total Shares. Except for the Shares and the options to acquire Shares set forth on the signature page hereto, such Shareholder does not beneficially own or have sole voting power with respect to any (i) shares of capital stock or voting securities of CVB, (ii) securities of CVB convertible into or exchangeable for shares of capital stock or voting securities of CVB or (iii) options or other rights to acquire from CVB any capital stock, voting securities or securities convertible into or exchangeable for capital stock or voting securities of CVB.

Section 2.05. Finder’s Fees. Except as provided in Section 5.17 of the Merger Agreement, no investment banker, broker, finder or other intermediary is entitled to a fee or commission from CVB in respect of this Agreement as a result of any arrangement or agreement made by or on behalf of such Shareholder.

3

ARTICLE 3

REPRESENTATIONS AND WARRANTIES OF PARENT

Parent represents and warrants to each Shareholder that:

Section 3.01 Valid Existence; Authorization. Parent is duly incorporated as a corporation, validly existing and in good standing under the laws of the Commonwealth of Virginia and has all corporate powers and all governmental licenses, authorizations, permits, consents and approvals required to carry on its business as now conducted. The execution, delivery and performance by Parent of this Agreement and the consummation by Parent of the transactions contemplated hereby are within the corporate powers of Parent and have been duly authorized by all necessary corporate action on the part of Parent. This Agreement has been duly and validly authorized, executed and delivered by Parent and constitutes a valid and binding agreement of Parent (assuming the due authorization, execution and delivery hereof by the Shareholders).

Section 3.02 Non-Contravention. The execution, delivery and performance by Parent of this Agreement and the consummation of the transactions contemplated hereby do not and will not (i) violate any applicable law, rule, regulation, judgment, injunction, order or decree, (ii) require any consent or other action by any Person under, constitute a default under, or give rise to any right of termination, cancellation or acceleration or to a loss of any benefit to which Parent is entitled under any provision of any agreement or other instrument binding on Parent or (iii) result in the imposition of any Lien on any asset of Parent.

ARTICLE 4

COVENANTS OF THE SHAREHOLDERS

Each Shareholder hereby severally covenants and agrees that so long as this Agreement is in effect:

Section 4.01. No Proxies for or Encumbrances on Shares. Except pursuant to the terms of this Agreement, such Shareholder shall not, without the prior written consent of Parent, directly or indirectly, (i) grant any proxies or enter into any voting trust or other agreement or arrangement with respect to the voting of any of such Shareholder’s Shares or (ii) acquire, Transfer, encumber or otherwise dispose of, or enter into any contract, option or other arrangement or understanding with respect to the direct or indirect acquisition or Transfer, encumbrance or other disposition of, any Shares, prior to the termination of this Agreement. Such Shareholder shall not seek or solicit any such acquisition or Transfer, encumbrance or other disposition or any such contract, option or other arrangement or understanding and agrees to notify Parent promptly, and to provide all details requested by Parent, if such Shareholder shall be approached or solicited, directly or indirectly, by any Person with respect to any of the

4

foregoing. In the event that pursuant to Section 7.05(b)(i) of the Merger Agreement the Board of Directors of CVB engages in negotiations or discussions with a Third Party that has made a written bona fide Acquisition Proposal that the Board of Directors of CVB determines will lead to a Superior Proposal, subject to compliance by CVB with the terms of the Merger Agreement, including without limitation Section 7.05 thereof, and subject to compliance by such Shareholder with the terms of this Agreement, nothing in the immediately preceding sentence shall prohibit such Shareholder from engaging in negotiations or discussions with such Third Party regarding such Shareholder entering into (concurrently with or subsequent to the termination of the Merger Agreement pursuant to Section 11.01(d)(i) thereof) (i) a voting agreement, (ii) an agreement with respect to granting a proxy or (iii) an agreement with respect to the sale of such Shareholder’s Shares, in each case with respect to such Acquisition Proposal. As used herein, the term “Transfer” shall mean, with respect to any security, the direct or indirect assignment, sale, transfer, tender, pledge, hypothecation, or the gift or other disposition of such security (excluding transfers by testamentary or intestate succession or otherwise by operation of law) or any right, title or interest therein (including, but not limited to, any right or power to vote to which the holder thereof may be entitled, whether such right or power is granted by proxy or otherwise), or the record or beneficial ownership thereof.

Section 4.02. Other Offers. Subject to Section 5.11, such Shareholder shall not directly or indirectly take any action that is prohibited under Section 7.05(a)(i) or (ii) of the Merger Agreement with respect to actions to be taken by CVB. Such Shareholder will promptly advise and update Parent after receipt by such Shareholder of an Acquisition Proposal related to the Shares in accordance with the notice provisions applicable to CVB as set forth in Section 7.05 of the Merger Agreement.

Section 4.03. Stop Transfer. Each Shareholder agrees with, and covenants to, Parent that such Shareholder will not request that CVB register the transfer (book-entry or otherwise) of any certificate or uncertificated interest representing any of the Shares, unless such transfer is made in compliance with this Agreement or to CVB.

ARTICLE 5

MISCELLANEOUS

Section 5.01. Further Assurances. Parent and each Shareholder will each execute and deliver, or cause to be executed and delivered, all further documents and instruments and use its best efforts to take, or cause to be taken, all actions and to do, or cause to be done, all things necessary, proper or advisable under applicable laws and regulations, to consummate and make effective the transactions contemplated by this Agreement.

5

Section 5.02. Amendments; Termination. Any provision of this Agreement may be amended or waived if, but only if, such amendment or waiver is in writing and is signed, in the case of an amendment, by each party to this Agreement or, in the case of a waiver, by the party against whom the waiver is to be effective. This Agreement shall terminate upon the earliest of (a) the Effective Time and (b) termination of the Merger Agreement in accordance with its terms, and all rights or obligations of the parties under this Agreement shall immediately terminate, except as provided in Section 5.11 hereof.

Section 5.03. Expenses. All costs and expenses incurred in connection with this Agreement shall be paid by the party incurring such cost or expense.

Section 5.04. Successors and Assigns; Obligations of Shareholders. The provisions of this Agreement shall be binding upon and inure to the benefit of the parties hereto and their respective successors and assigns; provided that no party may assign, delegate or otherwise transfer any of its rights or obligations under this Agreement without the consent of the other parties hereto, except that Parent may transfer or assign its rights and obligations to any Affiliate of Parent.

Section 5.05. Governing Law. This Agreement shall be construed in accordance with and governed by the laws of the Commonwealth of Virginia.

Section 5.06. Counterparts; Effectiveness. This Agreement may be signed in any number of counterparts, each of which shall be an original, with the same effect as if the signatures thereto and hereto were upon the same instrument. This Agreement shall become effective as between Parent, on the one hand, and a Shareholder, on the other hand, when each such party shall have received counterparts hereof signed by each such other party.

Section 5.07. Severability. If any term, provision or covenant of this Agreement is held by a court of competent jurisdiction or other authority to be invalid, void or unenforceable, the remainder of the terms, provisions and covenants of this Agreement shall remain in full force and effect and shall in no way be affected, impaired or invalidated.

Section 5.08. Specific Performance; Injunctive Relief. The parties hereto agree that Parent would suffer irreparable damage and that there will be no adequate remedy at law (including monetary damages) in the event any provision of this Agreement is not performed in accordance with the terms hereof and that the parties shall be entitled to specific performance of the terms hereof, injunctive relief and any other remedy to which they are entitled at law or in equity.

Section 5.09. Capitalized Terms. Capitalized terms used but not defined herein shall have the respective meanings set forth in the Merger Agreement.

Section 5.10. Notices. All notices, requests, claims, demands and other communications under this Agreement shall be in writing and shall be deemed given if delivered personally or sent by overnight courier (providing proof of

6

delivery) to the parties at the following addresses (or at such other address for a party as shall be specified by like notice): (i) if to Parent, to the appropriate address for notice thereto set forth in the Merger Agreement and (ii) if to a Shareholder, to the appropriate address set forth underneath such Shareholder’s name on the signature pages hereto.

Section 5.11. Shareholder Capacity. No person executing this Agreement who is or becomes during the term hereof a director or officer of CVB makes any agreement or understanding herein in his capacity as such director or officer. Each Shareholder signs solely in his capacity as the record holder and beneficial owner of such Shareholder’s Shares and nothing in this Agreement shall limit or affect any actions taken by any Shareholder in his capacity as an officer or director of CVB. This Section 5.11 shall survive termination of this Agreement.

7

IN WITNESS WHEREOF, the parties hereto have caused this Agreement to be duly executed as of the day and year first above written.

10

11

12

13

14

15

16

17

18

Exhibit A

SHAREHOLDERS

Robert L. Bailey

Hal D. Bourque

Charles F. Dawson

Joseph F. Fary

William D. Fary

Walter H. Graham

Walter B. Hurley, Jr.

Joseph A. Lombard, Jr.

Kenneth E. Smith

David G. Walker