Exhibit 99.4

LETTER TO CLIENTS OF NOMINEE HOLDERS

EASTERN VIRGINIA BANKSHARES, INC.

1,098,901 Shares of Common Stock

Offered Pursuant to Rights Distributed to Record Shareholders of

Eastern Virginia Bankshares, Inc.

To Our Clients:

Enclosed for your consideration is the Prospectus, dated May [__], 2013 (the “Prospectus”), relating to the offering (the “Rights Offering”) by Eastern Virginia Bankshares, Inc. (the “Company”) of shares of its Common Stock, par value $2.00 per share (the “Common Stock”), pursuant to non-transferable subscription rights (the “Rights”) distributed to all holders of record of shares of Common Stock, at 5:00 pm, Eastern time, on May 3, 2013 (the “Record Date”). The Rights are described in the Prospectus.

In the Rights Offering, the Company is offering an aggregate of 1,098,901 shares of its Common Stock (the “Underlying Shares”) pursuant to the Prospectus. The Rights will expire, if not exercised, at 5:00 p.m., Eastern time, on Friday, June 14, 2013, unless extended by the Board of Directors of the Company (as it may be extended, the “Expiration Date”).

As described in the accompanying Prospectus, you will receive one Right for every share of Common Stock carried by us in your account as of the Record Date.

Each Right allows the holder thereof to subscribe for 0.181051448 of a share of Common Stock (the “Basic Subscription Right”) at the cash price of $4.55 per whole share (the “Subscription Price”), subject to the Company’s right to limit the beneficial ownership of any individual shareholder to no more than 4.9% (unless such shareholder’s beneficial ownership exceeded 4.9% on the Record Date for the Rights Offering) (the “4.9% Rights Offering Restriction”). Fractional shares or cash in lieu of fractional shares will not be issued in the Rights Offering. Instead, fractional shares resulting from the exercise of the Basic Subscription Right will be eliminated by rounding down to the nearest whole share. As an example, if you owned 1,000 shares of Common Stock as of the Record Date, you would receive 1,000 Rights pursuant to your Basic Subscription Right that would entitle you to purchase 181 shares of common stock (181.051448 rounded down to the nearest whole share) at the Subscription Price of $4.55 per whole share, subject to the 4.9% Rights Offering Restriction.

A holder of Rights may exercise all or a portion of the Basic Subscription Right, subject to the 4.9% Rights Offering Restriction, or may choose not to exercise any of the Basic Subscription Right. However, if a holder of Rights does not fully exercise the Basic Subscription Right, such holder will not be entitled to purchase Excess Shares (as defined below) under the Over-subscription Privilege (as defined below).

In addition to the Basic Subscription Right, each holder of Rights who exercises his Basic Subscription Right in full will be eligible, subject to the 4.9% Rights Offering Restriction, to subscribe (the “Over-subscription Privilege”) at the same Subscription Price of $4.55 per whole share for additional shares of Common Stock if any Underlying Shares are not purchased by other holders of Rights under their Basic Subscription Rights as of the Expiration Date (the “Excess Shares”). Each holder of Rights may exercise his Over-subscription Privilege only if he exercised his Basic Subscription Right in full and other holders of Rights do not exercise their Basic Subscription Rights in full. If there is not a sufficient number of Excess Shares to satisfy all requests for subscriptions made under the Over-subscription Privilege, the Company will allocate the remaining Excess Shares pro rata, after eliminating all fractional shares, among those Rights holders who exercised their Over-subscription Privileges in proportion to the number of shares of Common Stock owned by such Right holder on the Record Date, relative to the number of shares of Common Stock owned on the Record Date by all Right holders exercising their Over-subscription Privilege, subject to the 4.9% Rights Offering Restriction. If this pro rata allocation results in any person receiving a greater number of Excess Shares than the person subscribed for pursuant to the exercise of the Over-subscription Privilege, then such person will be allocated only that number of Excess Shares for which the person over-

subscribed, subject to the 4.9% Rights Offering Restriction, and the remaining Excess Shares will be re-allocated among all other persons exercising the Over-subscription Privilege on the same pro rata basis described above. The proration process will be repeated until all Excess Shares have been allocated.

For the purposes of determining their eligibility for the Over-subscription Privilege, holders will be deemed to have exercised their Rights under the Basic Subscription Right in full if they subscribe for the maximum number of whole Underlying Shares available under their Basic Subscription Right. See “The Rights Offering—The Subscription Rights” in the Prospectus.

THE MATERIALS ENCLOSED ARE BEING FORWARDED TO YOU AS THE BENEFICIAL OWNER OF COMMON STOCK CARRIED BY US IN YOUR ACCOUNT BUT NOT REGISTERED IN YOUR NAME. EXERCISES OF RIGHTS MAY BE MADE ONLY BY US AS THE RECORD OWNER AND PURSUANT TO YOUR INSTRUCTIONS. Accordingly, we request instructions as to whether you wish us to elect to subscribe for any shares of Common Stock to which you are entitled pursuant to the terms and subject to the conditions set forth in the enclosed Prospectus. However, we urge you to read the Prospectus and other enclosed materials carefully before instructing us to exercise your Rights.

Your instructions to us should be forwarded as promptly as possible in order to permit us to exercise Rights on your behalf in accordance with the provisions of the Rights Offering. The Rights Offering will expire at 5:00 p.m., Eastern time, on the Expiration Date. Once you have exercised your Rights under the Basic Subscription Privilege and the Over-Subscription Privilege, such exercise may not be canceled, revoked or otherwise amended.

If you wish to have us, on your behalf, exercise the Rights for any shares of Common Stock to which you are entitled, please so instruct us by timely completing, executing and returning to us the Beneficial Owner Election form attached to this letter.

With respect to any instructions to exercise (or not to exercise) Rights, the enclosed Beneficial Ownership Election must be completed and returned such that it will be actually received by us by 5:00 p.m., Eastern time, on Thursday, June 13, 2013, the last business day prior to the scheduled expiration date of the Rights Offering of Friday, June 14, 2013 (which may be extended by the Board of Directors of the Company).

ANY QUESTIONS OR REQUESTS FOR ASSISTANCE CONCERNING THE RIGHTS OFFERING SHOULD BE DIRECTED TO EAGLE ROCK PROXY ADVISORS, LLC, THE INFORMATION AGENT, AT THE FOLLOWING TOLL-FREE TELEPHONE NUMBER: (888) 669-2032.

2

BENEFICIAL OWNER ELECTION

The undersigned acknowledge(s) receipt of your letter and the enclosed materials referred to therein relating to the offering of shares of Common Stock of Eastern Virginia Bankshares, Inc. (the “Company”).

With respect to any instructions to exercise (or not to exercise) Rights, the undersigned acknowledges that this form must be completed and returned such that it will actually be received by you by 5:00 p.m., Eastern time, on Thursday, June 13, 2013, the last business day prior to the scheduled expiration date of the Rights Offering of Friday, June 14, 2013 (which may be extended by the Board of Directors of the Company).

This will instruct you whether to exercise Rights to purchase shares of the Company’s Common Stock distributed with respect to the shares of the Company’s Common Stock held by you for the account of the undersigned, pursuant to the terms and subject to the conditions set forth in the Prospectus.

Box 1. ¨ Please DO NOT EXERCISE RIGHTS for shares of Common Stock.

Box 2. ¨ Please EXERCISE RIGHTS for shares of Common Stock as set forth below.

The number of Rights for which the undersigned gives instructions for exercise under the Basic Subscription Privilege should not exceed the number of Rights that the undersigned is entitled to exercise.

Box 3. ¨ Payment in the following amount is enclosed $                     

Box 4. ¨ Please deduct payment from the following account maintained by you as follows:

Date:                     , 2013