VOTING AGREEMENT

Exhibit 10.1

VOTING AGREEMENT

This Voting Agreement (this “Agreement”) dated February 10, 2005 is entered into among Velocity Express Corporation, a Delaware corporation (the “Company”), and Special Situations Fund III, L.P., Special Situations Cayman Fund, L. P., Special Situations Private Equity Fund, L.P., Scorpion Capital Partners, L.P., Scorpion Acquisition, LLC, Pequot Scout Fund, L.P., Pequot Navigator Onshore Fund, L.P., Pequot Navigator Offshore Fund, Inc., Premium Series PCC Limited – Cell 33, TH Lee Putnam Ventures, L.P., TH Lee Putnam Parallel Ventures, L.P., THLi Coinvestment Partners, LLC, Blue Star I, LLC, Jack Duffy, Dolph DiBiaso, Vincent Wasik, Palm Beach Overseas Investors, Limited, Andrew Boszhardt, BNS Long Short Fund, William S. Lapp, Steven Cristaldi, Alexander Paluch, Ray A. Mirza, BPEF 2 Pegasus Limited, East River II, L.P. and TerraNova Capital (each individually a “Stockholder” and collectively, the “Stockholders”).

In consideration of the mutual promises made herein and for other good and valuable consideration, the receipt and sufficiency of which are hereby acknowledged, the parties hereto hereby agree as follows:

1. Certain Definitions.

As used in this Agreement, the following terms shall have the following meanings:

“Common Stock” means the common stock, $0.004 par value per share, of the Company.

“Effective Date” means the date of this Agreement.

“Excess Shares” means, with respect to any Stockholder at any time, the shares of Preferred Stock constituting the difference obtained by subtracting (i) the Voting Shares held by such Stockholder from (ii) the total Preferred Shares held by such Stockholder. The number of Excess Shares held by each Stockholder (other than TerraNova Capital) as of the date hereof, assuming that the Preferred Shares were issued on the same day the Stockholder entered into the Purchase Agreement, is set forth on Schedule 1 appended hereto.

“Nasdaq” means The Nasdaq Stock Market or any successor thereto.

“Purchase Agreement” means that certain Purchase Agreement, dated as of December 21, 2004, by and among the Company and certain of the Stockholders.

“Preferred Shares” means shares of Series M Convertible Preferred Stock, $0.004 par value per share, of the Company. The number of Preferred Shares held by each Stockholder (other than TerraNova Capital) as of the date hereof, assuming that the Preferred Shares were issued on the same day the Stockholder entered into the Purchase Agreement, is set forth on Schedule 1 appended hereto.

“Voting Shares” means, with respect to any Stockholder at any time, the Preferred Shares constituting the product (rounded off to the nearest whole number, with fractional

amounts equal to 0.50 rounded up) obtained by multiplying (i) the total Preferred Shares held by such Stockholder, including Preferred Shares received as dividend on other Preferred Shares, by (ii) 0.30708. The number of Voting Shares held by each Stockholder (other than TerraNova Capital) as of the date hereof, assuming that the Preferred Shares were issued on the same day the Stockholder entered into the Purchase Agreement, is set forth on Schedule 1 appended hereto. The parties hereto acknowledge and agree that any and all of the Stockholders may agree to deem any number of Voting Shares held by any Stockholder party to such agreement to be Excess Shares and an equal number of Excess Shares held by any Stockholder party to such agreement to be Voting Shares; provided, that, the total number of Voting Shares held by such Stockholders after such agreement does not exceed the total number of Voting Shares held by such Stockholders prior to such agreement. No such agreement shall be effective unless and until the Company has received written notice (executed by all Stockholders party to such agreement) thereof.

2. Voting. Each Stockholder covenants and agrees that, from and after the Effective Date and until the termination of this Agreement in accordance with the terms hereof (the “Term”), at any meeting of stockholders of the Company, however called, and in any action by written consent of stockholders of the Company, such Stockholder will not vote, or cause to be voted (by means of proxy, voting trust, voting agreement or otherwise), Preferred Shares, other than the Voting Shares held by such Stockholder, on any matter on which the holders of Preferred Shares vote together with the holders of the Common Stock (and any other class or series of capital stock of the Company) as a single class. When voting the Voting Shares on any matter on which the holders of Preferred Shares vote together with the holders of the Common Stock (and any other class or series of capital stock of the Company) as a single class, each Stockholder covenants and agrees that, during the Term, the voting rights under the Voting Shares shall be calculated without regard to the adjustment of conversion price pursuant to Section 4C of the Certificate of Designation of the Preferred Shares. Notwithstanding the foregoing, nothing in this Agreement shall restrict any Stockholder from voting or causing to be voted at any meeting of stockholders of the Company or in any action by written consent of stockholders of the Company (i) any Preferred Shares (including, without limitation, any Excess Shares) on any matter upon which the holders of Preferred Shares are voting as a separate class, solely to the extent such holders of Preferred Shares are voting as a separate class and (ii) any shares of Common Stock, whether acquired upon conversion of Preferred Shares or otherwise.

3. Term. This Agreement shall become effective on the Effective Date. This Agreement shall terminate as to any Stockholder (i) upon receipt by the Company of written notification from Nasdaq that the ownership and voting of the Preferred Shares (including, without limitation, the Excess Shares) by the Stockholders does not conflict with Nasdaq Marketplace Rule 4351 or any successor thereto, (ii) upon the conversion of all Preferred Shares owned by such Stockholder into Common Stock pursuant to the terms of the Preferred Shares or (iii) upon such Stockholder no longer owning any Preferred Shares.

4. Legend. Each certificate representing Preferred Shares held by a Stockholder shall bear a legend substantially in the following form:

“The securities represented by this certificate are subject to a voting agreement with Velocity Express Corporation, a copy of which is available for inspection at the office of the Secretary of Velocity Express Corporation.”

Promptly following the execution of this Agreement, each Stockholder will return to the Company any and all certificates representing shares held by such Stockholder so that the Company may place thereon the legend required by this Section 4. The legend required by this Section 4 shall be removed from certificates representing Preferred Shares held by a Stockholder at the request of such Stockholder, upon the termination of this Agreement and the delivery to the Company of such certificates.

5. No Revocation. This Agreement shall be deemed to be coupled with an interest and may not be revoked, except with the written consent of the Company.

6. Successors and Assigns. This Agreement shall inure to the benefit of the successors and assigns of the Company and be binding upon the Stockholders and each of their respective heirs, executors, administrators, successors and assigns. Any sale or other transfer of any Preferred Shares shall be null and void, unless and until the transferee agrees in a writing, delivered to the Company, to be bound by the terms of this Agreement, which writing shall also contain notice to the Company of such transfer and of the notice information for such transferee.

7. No Other Issuances Outside this Agreement. The Company and the Stockholders agree that no issuance of Preferred Shares shall be made unless and until the recipient of the Preferred Shares are bound by the terms of this Agreement or agrees in a writing, delivered to the Company, to be bound by the terms of this Agreement.

8. Specific Performance. The parties hereto agree that irreparable damage would occur in the event any provision of this Agreement were not performed in accordance with the terms hereof. In the event of any breach of this Agreement, in addition to any and all other remedies available at law, the parties hereto shall be entitled to specific performance of this Agreement and to such other injunctive or equitable remedy as may be granted by a court of competent jurisdiction.

9. Notices. All notices and other communications provided for or permitted under this Agreement shall be made as set forth in Section 9.4 of the Purchase Agreement.

10. Amendment. Any term of this Agreement may be amended and the observance of any term of this Agreement may be waived (either generally or in a particular instance and either retroactively or prospectively), only with the written consent of the Company and the holders of at least 80% of the Preferred Shares then subject to this Agreement. Any amendment of waiver effected in accordance with this Section 10 shall be binding upon each holder of Preferred Shares, each future holder of all such Preferred Shares and the Company.

11. Applicable Law. This Agreement shall be governed by and construed in accordance with, the laws of the State of Delaware without regard to principles of conflicts of laws.

12. Severability. Any provision of this Agreement that is prohibited or unenforecable in any jurisdiction shall, as to such jurisdiction, be ineffective to the extent of such prohibition or unenforceability without invalidating the remaining provisions hereof but shall be interpreted as if it were written so as to be enforceable to the maximum extent permitted by applicable law, and any such prohibition or unenforceability in any jurisdiction shall not invalidate or render unenforceable such provision in any other jurisdiction. To the extent permitted by applicable law, the parties hereto hereby waive any provision of law which renders any provisions hereof prohibited or unenforceable in any respect.

13. Counterparts. This Agreement may be executed in two or more counterparts, each of which shall be deemed an original, but all of which together shall constitute one and the same instrument. This Agreement may also be executed via facsimile, which shall be deemed an original.

14. Entire Agreement. This Agreement represents the complete agreement of the parties hereto with respect to the subject matter hereof and supersedes all prior agreements and understandings relating to the subject matter hereof.

15. Conflicts. If there is any conflict between the terms of this Agreement and the Purchase Agreement (or any agreement entered into pursuant to the Purchase Agreement), the terms of this Agreement shall control.

16. Titles and Subtitles. The titles and subtitles used in this Agreement are used for convenience only and are not to be considered in construing or interpreting this Agreement.

IN WITNESS WHEREOF, the parties hereto have executed this Agreement as of the date first above written.

SCHEDULE 1

Preferred Shares, Voting Shares and Excess Shares