WAIVER AND CONSENT AGREEMENT

Exhibit 10.4

July 28, 2006

WAIVER AND CONSENT AGREEMENT

Waiver for Issuance of Additional Series Q Preferred. Reference is made to the Purchase Agreement dated July 3, 2006 (the “Purchase Agreement”), relating to the sale of 12% Senior Secured Notes due 2010/Warrants to Purchase Common Stock of Velocity Express Corporation (the “Company”).

Concurrent with entering into the Purchase Agreement and the sale of the Senior Secured Notes and Warrants, the Company sold $40.0 million of Series Q Convertible Preferred Stock (the “Series Q Preferred”) in a private placement transaction. The Company had indications of interest for the sale of up to an additional $5.0 million of Series Q Preferred, but was unable to complete the sale of the Series Q Preferred on the date of closing the Purchase Agreement. The Company desires to sell up to $5.0 million of additional Series Q Preferred at $10.00 per share and on the same terms and conditions as the Series Q Preferred was sold to other investors. The sale of such additional Series Q Preferred will enhance the Company’s capital structure.

Section 4(n) of the Purchase Agreement provides that during the period between July 3, 2006 and the consummation of the merger contemplated by the Company’s merger agreement with CD&L, Inc., the Company will not issue or sell any shares of its capital stock or securities exercisable for, exchangeable for or convertible into shares of capital stock except for capital stock issued pursuant to the terms of outstanding rights or convertible securities or grants of options to employees pursuant to the Company’s stock option plans.

In addition, Section 12(b) of the Warrant issued to each purchaser of the Senior Secured Notes provides that if the Company issues or sells any shares of capital stock of the Company without consideration or for a consideration per share less than the Current Market Price (as defined in the Warrant), a “Trigger Issuance” results, requiring an adjustment to the exercise price and number of shares issuable upon exercise of the Warrant.

In consideration of the Company’s request and the investment in the Company’s Series Q Preferred by additional investors, you agree to waive the provisions of Section 4(n) of the Purchase Agreement and waive a Trigger Issuance adjustment of the purchase price and number of shares issuable pursuant to the Warrants, as provided in Section 12(b) of the Warrant, with respect to the Company’s proposed sale of up to $5.0 million of additional Series Q Preferred and any conversion shares or payment in kind dividends issued pursuant thereto.

Consent to Indenture Amendment. Reference is made to the Indenture dated July 3, 2006, between the Company and Wells Fargo Bank, N.A., as trustee, pursuant to which the Company issued its 12% Senior Secured Notes due 2010 in the principal amount of $78,205,000.

Contemporaneously with the Company’s contemplated merger with CD&L, Inc., the Company is obligated under the Indenture to satisfy all indebtedness of CD&L. That indebtedness includes four promissory notes in an aggregate principal amount of approximately $1,700,000 (the “CD&L Seller Notes”) and a letter of credit issued by Bank of America for the account of CD&L in the approximate amount of $3,700,000 (the “CD&L Letter of Credit”). The Company wishes to satisfy some or all of the CD&L Seller Notes by issuing up to $1,800,000 Additional Notes (as defined in the Indenture), together with Warrants to purchase the Company’s common stock at a price of $1.45 per share in an amount of 345 shares for each $1,000 principal amount of Additional Notes (the “Additional Warrants”), to any willing holders of the CD&L Seller Notes. The Company wishes to cash collateralize the CD&L Letter of Credit until it puts in place a working capital line of credit under which a replacement letter of credit would be issued. You consent to amendments to the Indenture necessary to permit the Company to issue such Additional Notes and cash collateralize the CD&L Letter of Credit, including amendments substantially on the terms set forth on Annex I attached to this Waiver and Consent Agreement.

Waiver for Issuance of Additional Notes and Additional Warrants.

As noted above, Section 4(n) of the Purchase Agreement provides that during the period between July 3, 2006 and the consummation of the merger contemplated by the Company’s merger agreement with CD&L, Inc., the Company will not issue or sell any shares of its capital stock or securities exercisable for, exchangeable for or convertible into shares of capital stock except for capital stock issued pursuant to the terms of outstanding rights or convertible securities or grants of options to employees pursuant to the Company’s stock option plans.

Also as noted above, Section 12(b) of the Warrant issued to each purchaser of the Senior Secured Notes provides that if the Company issues or sells any shares of capital stock of the Company without consideration or for a consideration per share less than the Current Market Price (as defined in the Warrant), a “Trigger Issuance” results, requiring an adjustment to the exercise price and number of shares issuable upon exercise of the Warrant.

In consideration of the Company’s request and the investment in the Additional Notes and Additional Warrants, you agree to waive the provisions of Section 4(n) of the Purchase Agreement and waive a Trigger Issuance adjustment of the purchase price and number of shares issuable pursuant to the Warrants, as provided in Section 12(b) of the Warrant, with respect to the Company’s proposed issuance of up to $1.8 million of Additional Notes and Additional Warrants and any shares issued pursuant thereto.

2

Please signify your agreement by signing below and returning this Waiver and Consent Agreement to the undersigned.

The undersigned represents that it is the registered holder of Warrants and the beneficial owner of Senior Secured Notes in the principal amount of $             .

The undersigned hereby agrees to the waivers of Section 4(n) of the 12% Senior Secured Security Notes Due 2010/Warrants to Purchase Common Stock Purchase Agreement, dated July 3, 2006, and waivers of the Trigger Adjustment contained in Section 12(b) of the Warrant issued pursuant to such Purchase Agreement as set forth in the foregoing waiver request letter of Velocity Express Corporation.

The undersigned hereby consents to amendments to the Indenture necessary to permit the Company to issue up to $1,800,000 in Additional Notes to the holders of CD&L Seller Notes and cash collateralize the CD&L Letter of Credit, including amendments substantially on the terms attached to this Waiver and Consent Agreement as Annex I.

3

ANNEX I TO WAIVER AND CONSENT AGREEMENT

Form of Certain Proposed Amendments to Indenture

Velocity Express Corporation

12% Senior Notes Due 2010

I. New Definitions

“CD&L Seller Notes” means the “Seller Notes” as defined in the Target Merger Agreement, consisting of four promissory notes in an aggregate principal amount of approximately $1,700,000.

“Cash Collateralized CD&L Letter of Credit” means that certain irrevocable letter of credit issued by Bank of America, N.A., for the account of CD&L, Inc., in the amount of $3,800,000.

“First Additional Notes” means Additional Notes issued to the holders of one or more of the CD&L Seller Notes contemporaneously with the Merger Closing in satisfaction of, and in principal amount not to exceed, the indebtedness evidenced by such CD&L Seller Notes.

II. Revised Definitions

“Additional Notes” means any additional 12% Senior Secured Notes Due 2010, issued by the Company in accordance with, and subject to the limitations contained in, Section 2.01(b), having the same terms in all respects as the Notes issued on the Issue Date, except that interest will accrue on the Additional Notes from the later of the most recent date to which interest has been paid on the Notes (other than Additional Notes) or if no interest has been paid, from the Issue Date December 30, 2006. Except as aforesaid, all Additional notes shall be treated as a single class of securities, as amended from time to time in accordance with the terms hereof, as the Notes issued pursuant to this Indenture on and from the Issue Date.

“Merger Closing” shall mean the effective date and time of consummation of the Target Merger in all significant respects in accordance with the terms and conditions set forth in the Target Merger Agreement and related transaction documents substantially in the form made available to the Trustee and the Holders as the operative Target Merger documentation as of the Issue Date, such consummation occurring (x) only upon satisfaction of all conditions precedent to the Target Merger specified in the Target Merger Agreement without any party’s waiver or release thereof or accommodation, modification or side-arrangement with respect thereto and otherwise without amendment to, limitation on or impairment of any rights, remedies, interests, entitlements, obligations or liabilities of the Company and/or its Restricted Subsidiaries under or in connection with such Target Merger Agreement and/or the Target Merger generally, excluding, in each case, any of the foregoing that are/were of a purely administrative nature or have/had no more than a de minimus impact, if any, on the assets, liabilities, businesses, operations and/or financial condition of the Company and/or its Restricted Subsidiaries; and, after giving effect to the Target Merger, and (y) in circumstances where all Indebtedness of the Target and/or Target Subsidiaries other than the Cash Collateralized CD&L Letter of Credit shall have been (or, simultaneously with the Merger Closing, shall be) fully and finally paid off and discharged on or prior to the Target Merger Closing, and upon and after giving effect to the

4

Target Merger Closing, Target and each Target Subsidiary shall have duly and validly acceded to this Indenture as, and have guaranteed and assumed all corresponding Note Obligations imposed on, Subsidiary Guarantors in this Indenture and associated documentation governing or evidencing the Note Obligations.

“Permitted Liens”: revised clause (22) to provide as follows:

(22) a Lien on Cash pledged to secure the Cash Collateralized Letter of Credit and, from and after the Merger Closing, a Lien on Cash pledged to secure the Cash Collateralized CD&L Letter of Credit, in each case in an amount equal not to exceed 105% of the undrawn amount of such Letter of Credit; and

III. Amended Provisions

SECTION 2.01 Amount of Notes; Additional Notes; Use of Proceeds.

***

(b) The Company shall be entitled, subject to satisfaction of each of the conditions contained in the proviso hereto, to issue and sell in a single, one time offering Additional Notes that shall be fungible in all respects with and trade under the same CUSIP number as the Notes in a maximum additional principal amount not to exceed $10,000,000 (or such lesser amount as reflects the then-current accreted value of the originally-issued Notes relative to their aggregate initial value when first issued and outstanding on the Issue Date; provided that with respect to any Additional Notes other than the First Additional Notes (i) the Company may issue and sell such Notes in a single, one-time offering, (ii) the Company shall, in compliance with all applicable securities laws (including each of the Holder officers’ good faith and commercially-reasonable efforts in cooperating with the Company toward qualification of such offering for Regulation D or other applicable exceptions from registration), afford the Holders, ratably in proportion to the respective Note Obligations represented by each of them (with secondary opportunity for first-round purchasing Holders to acquire, in accordance with their relative Note Obligations vis-à-vis other second-round participating Holders, any or all unsubscribed Additional Notes from the first-round, pro-rata offering), a right of first purchase covering all such Additional Notes as may be offered, with purchase right shall be held open to the Holders for a period of not less than fifteen (15) Business Days after the Company’s initial notice to the Trustee of any such proposed offering; and (iii) no offering or sale whatsoever of such Additional Notes shall be permitted to be made unless and until (A) Consolidated Cash Flow shall equal or exceed $20,000,000 for the Covenant Reference Period; (B) the incurrence of the full Indebtedness amount represented by any and all Additional Notes then proposed for issuance will be made pursuant to the first paragraph of Section 4.09 and not result in any Default or breach of the Fixed Charge Coverage Ratio test or other covenant or requirement separately imposed under Article 4 or any other applicable provision(s) of this Indenture, the Notes and the Security Documents

5

and (C) the ratio of the Company’s consolidated secured Indebtedness, after giving pro forma effect to such incurrence and the immediate application of proceeds thereof calculated as required by Regulation S-X of the Exchange Act, to then-current stockholders’ equity is no worse than that as reported in the Company’s most-recent financial statements on file with the SEC (or, if applicable, any more-recent audited financial statements as are then available).

SECTION 4.09. Limitation on Incurrence of Additional Indebtedness and Issuance of Preferred Stock.

From and after the Issue Date:

(1) the Company will not, and will not permit any of its Restricted Subsidiaries to, incur any Indebtedness (including Acquired Debt and Indebtedness represented by the issuance of any Additional Notes);

(2) the Company will not, and will not permit any of its Restricted Subsidiaries to, issue any Disqualified Stock (including Acquired Disqualified Stock); and

(3) the Company will not permit any of its Restricted Subsidiaries that are not Subsidiary Guarantors to issue any shares of Preferred Stock (including Acquired Preferred Stock);

provided, however, that the Company and the Subsidiary Guarantors may incur Indebtedness (including Acquired Debt and Indebtedness represented by Additional Notes) and the Company and the Subsidiary Guarantors may issue shares of Disqualified Stock (including Acquired Disqualified Stock), provided that any such Indebtedness (other than Additional Notes) ranks junior to, and has a maturity date no earlier than 91 days after the Maturity Date of, the Notes (and any Additional Notes), if the Fixed Charge Coverage Ratio for the applicable Covenant Reference Period preceding the date on which such additional Indebtedness is incurred or such Disqualified Stock is issued would have been at least 2 to 1, determined on a pro forma basis and calculated as required by Regulation S-X of the Exchange Act (including a pro forma application of the net proceeds therefrom), as if the additional Indebtedness had been incurred or the Disqualified Stock had been issued, as the case may be, at the beginning of such Covenant Reference Period, with any letters of credit and bankers’ acceptances being deemed to have an aggregate principal amount of Indebtedness equal to the maximum amount available thereunder.

The immediately preceding paragraph will not apply to:

(i) the incurrence or existence of Indebtedness constituting, at any time on or after the Issue Date (but only as and when permitted to be incurred thereafter in accordance with all applicable conditions and limitations contained in Section 4.16 and in no event in an aggregate outstanding principal amount exceeding the Applicable Facility Cap), Senior Facility Obligations less 50% of the aggregate amount of any repayments of term Indebtedness under Senior

6

Facility Obligations and all repayments of revolving credit Indebtedness under such Senior Facility Obligations effected with a corresponding commitment reduction under such Senior Facility Obligation pursuant to clause (a) of the second paragraph of Section 4.12;

(ii) the incurrence by the Company and the Subsidiary Guarantors of Indebtedness represented by the Notes (excluding any Additional Notes) and the First Additional Notes and Subsidiary Guarantees thereof;

***

(x) (A) the reimbursement obligation evidenced by the Cash Collateralized CD&L Letter of Credit and (B) other Acquired Debt or Acquired Disqualified Stock; provided that such other Indebtedness or Disqualified Stock was not incurred in connection with or in contemplation of such Person becoming a Restricted Subsidiary; and provided further that immediately after giving effect to such incurrence, the Fixed Charge Coverage Ratio for the applicable Covenant Reference Period preceding the date of such incurrence would have been at least 2 to 1 or, if not, will have improved immediately thereafter, determined on a pro forma basis (including giving pro forma effect to the applicable transaction related thereto);

7