CONSENT, AMENDMENT AND WAIVER AGREEMENT

EXHIBIT 10.3

CONSENT, AMENDMENT AND WAIVER AGREEMENT

This CONSENT, AMENDMENT AND WAIVER AGREEMENT (this “Agreement”) is dated effective June 29, 2006, and entered into by and among Velocity Express Corporation, a Delaware corporation (the “Company”) and each of the stockholder signatories hereto constituting the holders (collectively, the “Holders”) of a majority of the issued and outstanding Series P Convertible Preferred Stock, par value $.004 per share (the “Series P Preferred Stock”).

W I T N E S S E T H:

WHEREAS, the Company and certain new investors (the “Series Q Purchasers”) intend to enter into a stock purchase agreement (the “Stock Purchase Agreement”) pursuant to which the Company will issue to the Series Q Purchasers up to 45,000,000 shares of the Company’s Series Q Convertible Preferred Stock, par value $.004 per share, (“Series Q Preferred Stock”) convertible into an equal number of shares of Common Stock, subject to adjustment, on the terms and conditions set forth in the Stock Purchase Agreement;

WHEREAS, the proposed Certificate of Designations, Preferences and Rights of the Series Q Preferred Stock provides for the payment of dividends thereon, at the option of the Company, in the form of shares of Series Q Preferred Stock (“PIK Shares”);

WHEREAS, certain rights and preferences set forth in the proposed Series Q Preferred Stock Certificate of Designations, Preferences and Rights are inconsistent with the rights and preferences of the Series P Preferred Stock, necessitating an amendment to the Certificate of Designations, Preferences and Rights of the Series P Preferred Stock;

WHEREAS, the Certificate of Designations, Preferences and Rights of the Series P Preferred Stock precludes the designation of the preferences and rights of the Series Q Preferred Stock and the issuance of the Series Q Preferred Stock in the absence of prior written consent from the holders of a majority of the Series P Preferred Stock;

WHEREAS, the purchase agreements governing the Company’s sale of the Series P Preferred Stock to the Holders provide for rights of participation and exchange applicable to the Company’s proposed issuance and sale of the Series Q Preferred Stock;

WHEREAS, the Company intends to enter into purchase agreements (the “Note and Warrant Purchase Agreements”) with certain investors (the “Senior Note Investors”), pursuant to which the Company will issue Senior Secured Notes (the “Notes”) and four-year warrants (each a “Note Warrant”) to purchase an aggregate of approximately 26,000,000 shares of Common Stock, subject to adjustment, at an exercise price of $1.45 per share, subject to adjustment;

WHEREAS, the execution and delivery of this Agreement by the parties hereto is a condition precedent to the Company entering into the Stock Purchase Agreement and the Note and Warrant Purchase Agreements;

WHEREAS, proceeds from the issuance and sale of the Series Q Preferred, the Notes and the Warrants, together with the issuance of shares of Common Stock, or securities convertible into or exercisable for Common Stock or a combination thereof with an aggregate fair value of approximately $3,200,000 (“Exeter Securities”) , will be used to effect the purchase of a portion of the issued and outstanding capital stock, and securities convertible into shares of the capital stock, of another company (the “Proposed Acquisition”);

WHEREAS, in connection with the transactions contemplated by the Stock Purchase Agreement and the Note and Warrant Purchase Agreements, the Company proposes to issue to Jefferies and Company, Broadband Capital, Meritage Funds and Terra Nova Trading, LLC, in payment of placement agent and finders fees, an aggregate of approximately 2,550,000 shares of Series Q Preferred Stock;

WHEREAS, the Company proposes to issue to TH Lee Putnam Ventures, a stockholder of the Company, warrants (“THLPV Warrants”) to purchase up to 250,000 and 547,500 shares, respectively, of Common Stock at a price of $.01 per share, in consideration for merger and acquisition services and credit enhancements in the form of loan guarantees provided to the Company;

WHEREAS, in connection with the Proposed Acquisition, the Company intends to issue: (i) warrants to purchase up to 400,000 shares of Common Stock at a price of $1.50 per share (the “Scura Rise Warrants”) to Scura Rise & Partners, LLC in satisfaction of investment banking fees; and (ii) up to approximately 500,000 shares of Common Stock to certain individuals in payment for consulting services;

WHEREAS, the Company proposes to issue 375,000 shares of Series Q Preferred Stock to Pequot Capital Management, a stockholder of the Company, in consideration for credit enhancements in the form of loan guarantees provided for the benefit of the Company;

WHEREAS, the shares of Common Stock issuable upon: (a) conversion of the Series Q Preferred Stock, (b) conversion of PIK Shares issuable as dividends on the Series Q Preferred Stock, (c) upon exercise of the Note Warrants, THLPV Warrants and Scura Rise Warrants, and (d) in connection with the Exeter Securities, together with the shares of Common Stock issuable in payment for consulting services: (i) will have aggregate voting power equal to or in excess of 20 percent of the voting power of the Company’s presently issued and outstanding shares of Common Stock; (ii) will have an aggregate share denomination equal to or in excess of 20 percent of the Company’s presently issued and outstanding shares of Common Stock; and (iii) may result in a change of control of the Company;

WHEREAS, in order to induce the Series Q Purchasers and the Senior Note Investors to consummate their proposed investment transactions for the benefit of all stockholders of the Company, including the Holders, the Company has requested, and the Holders have agreed, to enter into this Agreement; and

WHEREAS, it is the intent of the parties to this Agreement that the consents set forth herein are provided pursuant to, and in compliance with, Section 228 of the General Corporation Law of the state of Delaware.

2

NOW, THEREFORE, 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 agree as follows:

A G R E E M E N T:

(1) Consent, Waiver, and Amendment. Each of the undersigned Holders (together with the Company as to item (c) below) hereby:

(a) consents to the Company’s designation of the preferences and rights of the Series Q Preferred Stock, including without limitation the superiority of the Series Q Preferred Stock in right of preference as to dividends and distributions made upon the liquidation of the Company, and the issuance and sale of the Series Q Preferred Stock;

(b) consents to and ratifies the amendment to the Series P Certificate of Designations, Preferences and Rights set forth on Exhibit A attached hereto;

(c) consents to the establishment of a Conversion Price of $1.23 per share, subject to adjustment as a result of applicable future transactions, if any (but not pursuant to, or in connection with, any of the transactions described in the preceding paragraphs), in compliance with the terms of the Series P Certificate of Designations, Preferences and Rights, as amended;

(d) waives, in connection with the issuance and sale of the Series Q Preferred Stock the application of the Right of First Refusal on Future Financings set forth in Section 6 of the stock purchase agreement governing the sale of the Series P Preferred Stock to the Holder; and

(e) consents to an amendment of the stock purchase agreement governing the sale of the Series P Preferred Stock to the Holder to delete Section 6 thereof in its entirety effective upon the closing of the sale of the Series Q Preferred Stock contemplated by the Stock Purchase Agreement; and

(f) consents to an amendment of Section 2(a)(iii) of that certain Registration Rights Agreement, dated October 14, 2005, by and among the Company and each of the Investors (as defined therein), pursuant to which the following text is hereby inserted at the end of the sentence appearing in such Section 2(a)(iii): “; provided, however, that in connection with any underwritten Piggyback Registration of securities, the right of holders of Registrable Securities to participate in such registration shall be subject to: (i) the judgment of the managing underwriter regarding the number of Registrable Securities that may participate without adversely affecting the public offering; and (ii) the right of holders of Common Stock issued or issuable upon conversion of Series Q Preferred Stock to participate in the underwritten offering in priority over the holders of Registrable Securities.”

(2) Binding Effect; Indemnification. This Agreement has been duly executed and delivered by such Holder, and this Agreement is the valid and binding agreement of the Holder, enforceable against the Holder in accordance with its terms, subject to applicable bankruptcy, insolvency, fraudulent conveyance, reorganization, moratorium and similar laws affecting creditors’ rights and remedies generally and to general principles of equity. Holder

3

acknowledges and agrees that the provisions of this Agreement are enforceable against Holder, subject to the limitations referred to above, regardless of the effect of this Agreement on persons not a party hereto. Holder may not sell, transfer or otherwise dispose of, in any manner (“Transfer”) any shares of Series P Preferred Stock without delivering to the Company the written consent of the transferee binding the transferee to the terms and conditions of this Agreement and Holder shall indemnify the Company from and against any costs, expenses, liabilities, losses or damages of any other kind or nature arising from any Transfer of Holder’s shares of Series P Preferred Stock in contravention of this covenant.

(3) Representations and Warranties. Each Holder represents and warrants, severally and not jointly, to the Company as follows:

(a) Access to Information. Such Holder has been provided with any and all documents describing the proposed transactions contemplated by this Agreement requested by such Holder, and has been provided access to officers of the Company and other members of its management to obtain any other information deemed relevant to the Holder’s decision whether or not to enter into this Agreement.

(b) Valid Title, etc. With respect to the Series P Preferred Stock such Holder beneficially owns (as defined in Rule 13d-3 of the Securities and Exchange Act of 1934 (each a “Share” and collectively, the “Shares”) there are no restrictions on the rights of disposition pertaining thereto, except for any restrictions contemplated herein or arising under applicable securities laws, such Holder has exclusive power to vote, exclusive power of disposition and exclusive power to agree to all of the matters set forth in this Agreement, in each case with respect to all of such Holder’s Shares with no limitations, qualifications or restrictions on these rights. Each Holder represents that neither the Holder nor any of the Holder’s affiliates is party to or bound by any agreement with respect to the voting (by proxy or otherwise), sale or other disposition of the Shares (other than this Agreement).

(c) Non-Contravention. The execution and delivery of this Agreement by such Holder and the performance by such Holder of such Holder’s obligations under this Agreement: (i) are within such Holder’s powers, have been duly authorized by all necessary action (including any consultation, approval or other action by or with any other person), (ii) require no action by or in respect of, or filing with, any governmental body, agency, official or authority, and (iii) do not and will not contravene or constitute a default under, or give rise to a right of termination, cancellation or acceleration of any right or obligation of such Holder or to a loss of any material benefit of such Holder under, any provision of applicable law or regulation or of any agreement, judgment, injunction, order, decree, or other instrument binding on him or result in the imposition of any lien on any asset of such Holder other than any conflicts, breaches, violations, defaults, obligations, rights or losses that individually or in the aggregate would not: (x) impair the ability of such Holder to perform the Holder’s obligations under this Agreement or (y) prevent or delay the consummation of any of the transactions contemplated hereby.

4

(d) Notices. Any notices provided for in this Agreement shall be in writing and shall be either personally delivered, sent by reputable overnight courier service, faxed or mailed by first class mail, return receipt requested, to the recipient at the address below indicated:

if to the Company:

One Morningside Drive

Suite 200

Westport, CT 06880

Telecopy: (203)  ###-###-####

Attention: Edward Stone

if to a Holder:

At the address for such Holder as set forth in the records of the Company.

or such other address or to the attention of such other person as the recipient party shall have specified by prior written notice to the sending party. Any notice under this Agreement shall be deemed to have been given when so delivered, sent or mailed.

(4) Miscellaneous.

(a) Each Holder acknowledges and agrees that this Agreement constitutes a binding agreement of such Holder and that the Company may be irreparably damaged if for any reason such Holder fails to perform any of its obligations hereunder, and that the Company would not have an adequate remedy at law for money damages in that event. Accordingly, the Company will be entitled to specific performance and injunctive and other equitable relief to enforce the performance of this Agreement by the Holders. This provision is without prejudice to any other rights that the Company may have against any Holder for any failure to perform its respective obligations under this Agreement.

(b) Whenever possible, each provision of this Agreement shall be interpreted in such manner as to be effective and valid under applicable law, but if any provision of this Agreement is held to be invalid, illegal or unenforceable in any respect under any applicable law or rule in any jurisdiction, such invalidity, illegality or unenforceability shall not affect any other provision of this Agreement or any action in any other jurisdiction, but this Agreement shall be reformed, construed and enforced in such jurisdiction as if such invalid, illegal or unenforceable provision had never been contained herein.

(c) This Agreement may be executed in separate counterparts, each of which is deemed to be an original and all of which taken together constitute one and the same agreement.

(d) This Agreement, together with any Exhibit hereto, embodies the complete agreement and understanding among the parties concerning the subject matter hereof and supersedes and preempts any prior understandings, agreements or representations by or among the parties, written or oral, with respect to the subject matter hereof.

5

(e) Governing Law; Jurisdiction; Waiver of Jury Trial. THE PROVISIONS OF THIS AGREEMENT SHALL BE GOVERNED BY AND CONSTRUED IN ACCORDANCE WITH THE LAWS OF THE STATE OF NEW YORK (EXCLUDING ANY CONFLICT OF LAW RULE OR PRINCIPLE THAT WOULD REFER TO THE LAWS OF ANOTHER JURISDICTION). EACH PARTY HERETO IRREVOCABLY SUBMITS TO THE JURISDICTION OF ANY FEDERAL COURT LOCATED IN THE SOUTHERN DISTRICT OF THE STATE OF NEW YORK OR ANY NEW YORK STATE COURT, IN ANY ACTION OR PROCEEDING THAT IS OTHERWISE PERMITTED UNDER THIS AGREEMENT OR ANY OTHER AGREEMENT EXECUTED IN CONNECTION WITH THIS AGREEMENT, AND EACH PARTY HERETO HEREBY IRREVOCABLY AGREES THAT ALL CLAIMS IN RESPECT OF ANY SUCH ACTION OR PROCEEDING MUST BE BROUGHT AND/OR DEFENDED IN SUCH COURT. EACH PARTY HERETO HEREBY CONSENTS TO SERVICE OF PROCESS BY ANY MEANS AUTHORIZED BY THE APPLICABLE LAW OF THE FORUM IN ANY ACTION BROUGHT UNDER OR ARISING OUT OF THIS AGREEMENT, AND EACH PARTY HERETO IRREVOCABLY WAIVES, TO THE FULLEST EXTENT EFFECTIVELY, THE DEFENSE OF AN INCONVENIENT FORUM TO THE MAINTENANCE OF SUCH ACTION OR PROCEEDING IN ANY SUCH COURT. EACH PARTY HERETO HEREBY IRREVOCABLY AND UNCONDITIONALLY WAIVES, TO THE FULLEST EXTENT IT MAY LEGALLY AND EFFECTIVELY DO SO, TRIAL BY JURY IN ANY SUIT, ACTION OR PROCEEDING ARISING HEREUNDER.

(f) This Agreement shall be binding upon and inure solely to the benefit of: (i) each party hereto, (ii) the Series Q Purchasers, (iii) the Senior Note Investors, and (iv) all other proposed recipients of the Company’s securities identified herein, together with the respective successors, assigns and transferees of each of the above, and nothing in this Agreement, express or implied, is intended to or shall confer upon any other person any right, benefit or remedy of any nature whatsoever under or by reason of this Agreement.

(g) Confidentiality. Each Holder acknowledges that this Agreement and its terms, until otherwise disclosed by the Company are confidential information and that the Holder has received and will continue to receive additional confidential information regarding the Company. Accordingly, the Holders agree to use their reasonable efforts to prevent the unauthorized disclosure of any confidential information concerning the Company that has been or is disclosed to it or its agents in connection with the entry of the parties in to this Agreement and the transactions contemplated hereby. Notwithstanding the foregoing, any Holder may make confidential information available to the Holder’s counsel, accountants and financial advisors; provided, however, the disclosing Holder shall remain liable to the Company and all other parties hereto damaged by any unauthorized disclosure by the Holder’s representative.

(h) The descriptive headings contained in this Agreement are included for convenience of reference only and shall not affect in any way the meaning or interpretation of this Agreement.

(i) All costs and expenses incurred in connection with this Agreement will be paid by the party incurring such cost or expense.

(j) No amendment, modification or waiver shall be binding or effective with respect to any provision hereof without the prior written consent of the holders of at least a majority of the Series P Preferred Stock outstanding at the time such action is taken.

* * *

[SIGNATURE PAGES FOLLOW]

6

IN WITNESS WHEREOF, the undersigned have executed this Consent, Amendment and Waiver Agreement as of the dates indicated below.

EXHIBIT A

AMENDMENTS TO CERTIFICATE OF DESIGNATIONS, RIGHTS AND PREFERENCES

OF SERIES P CONVERTIBLE PREFERRED STOCK

Sections 2 and 3 of the Certificate of Designations, Rights and Preferences of Series P Convertible Preferred Stock set forth in the Certificate of Incorporation, as amended, is hereby amended by deleting Sections 2 and 3 in their entirety and replacing them with the following (changes from the current Certificate are marked):

2. Dividends.

(a) Each Holder of Series P Preferred Stock, in preference and priority to the Holders of all other classes of stock other than Holders of the Company’s Series M Convertible Preferred Stock (the “Series M Preferred”) and the Series Q Convertible Preferred Stock (the “Series Q Preferred”), shall be entitled to receive, with respect to each share of Series P Preferred Stock then outstanding and held by such Holder of Series P Preferred Stock, dividends, commencing from the date of issuance of such share of Series P Preferred Stock, at the rate of eight percent (8%) per annum of the Series P Stated Value (the “Series P Preferred Dividends”); provided, however, that from and after the Company’s issuance of not less than 36,000,000 shares of Series Q Preferred, the Series P Preferred dividend rate shall be reduced to six percent (6%) per annum. The Series P Preferred Dividends shall be cumulative, whether or not earned or declared, and shall be paid quarterly in arrears on the first day of February, May, August and November in each year. At the election of the Company, the Series P Preferred Dividends shall be paid by (a) issuing each Holder of Series P Preferred Stock such number of shares of Series P Preferred Stock equal to the Series P Preferred Dividend divided by the Series P Stated Value (“PIK Shares”), or (b) cash out of legally available funds therefor. Any election by the Company to pay dividends in shares of Series P Preferred Stock or cash shall be made uniformly with respect to all outstanding shares of Series P Preferred Stock for a given dividend period.

(b) No dividends shall be paid on any Common Stock of the Company or any other capital stock of the Company other than the Series M Preferred and the Series Q Preferred during any fiscal year of the Company until all outstanding Series P Preferred Dividends (with respect to the current fiscal year and all prior fiscal years) shall have been paid or declared and set apart for payment to the Holders of Series P Preferred Stock.

(c) In the event that the Company shall at any time pay a dividend on the Common Stock or any other class or series of capital stock of the Company other than the Series M Preferred and the Series Q Preferred, the Company shall, at the same time, pay to each Holder of Series P Preferred Stock a dividend equal to the dividend that would have been payable to such Holder if the shares of Series P Preferred Stock held by such Holder had been converted into Common Stock on the date of determination of Holders of Common Stock entitled to receive such dividends.

3. Liquidation; Redemption. Upon any liquidation, dissolution or winding up of the Company, whether voluntary or involuntary, the Holders of the shares of Series P Preferred Stock shall rank (i) senior to the Holders of the Common Stock and the Company’s Series N

A-1

Convertible Preferred Stock and Series O Convertible Preferred, (ii) junior to the Holders of Series Q Preferred, and (iii) on parity with the Holders of the Series M Preferred, as to such distributions, and shall be entitled to be paid an amount per share equal to the Series P Stated Value plus any accrued and unpaid Series P Preferred Dividends (the “Liquidation Preference”). No modification of this Liquidation Preference shall be made without the prior written approval of at least 62.5% of the then outstanding Series P Preferred. If upon such liquidation, dissolution or winding up of the Company, whether voluntary or involuntary, the assets to be distributed among the Holders of the Series P Preferred Stock and any class or Series P capital stock ranking on a parity with the Series P Preferred Stock as to such distributions shall be insufficient to permit payment to the Holders of the Series P Preferred Stock and any such class or series of capital stock of their respective liquidation amount, then the entire assets of the Company to be distributed shall be distributed pro rata to the Holders of Series P Preferred Stock and the Holders of such class or series of capital stock ranking on a parity with the Series P Preferred Stock as to such distributions according to the preferential amounts due thereon.

The definition of the term “Excluded Stock” appearing in Section 1 of the Certificate of Designations, Rights and Preferences of Series P Convertible Preferred Stock set forth in the Certificate of Incorporation, as amended, is hereby amended by replacing the word “and” which precedes “(C)” with a comma “,” and inserting at the end of the sentence: “and (D) any issuance of shares of Series M, N, O or Q Convertible Preferred Stock, including without limitation any issuance in payment of dividends with respect to the same series of preferred stock.”

The defined term “Event of Default” and the definition of such term appearing thereafter in Section 1 of the Certificate of Designations, Rights and Preferences of Series P Convertible Preferred Stock, together with Section 4(c) thereof are hereby stricken in their entirety.

A-2