FOURTH SUPPLEMENTAL INDENTURE

Exhibit 10.1

FOURTH SUPPLEMENTAL INDENTURE

THIS FOURTH SUPPLEMENTAL INDENTURE (this “ Fourth Supplemental Indenture ”) dated as of May 19, 2008, among VELOCITY EXPRESS CORPORATION, a Delaware corporation (the “ Company ”), and WILMINGTON TRUST, as successor to WELLS FARGO BANK, N.A. (the “ Trustee ”), to the INDENTURE, dated as of July 3, 2006, among the Company, the guarantors party thereto and the Trustee, pursuant to which the Company has issued and there remains outstanding $78,205,000 in aggregate principal amount of 12.0% Senior Secured Notes due 2010 (the “ Notes ”), as amended by the First Supplemental Indenture, dated as of August 17, 2006, the Second Supplemental Indenture, dated as of December 22, 2006 and the Third Supplemental Indenture dated as July 25, 2007 (as so amended by the First Supplemental Indenture, the Second Supplemental Indenture, and the Third Supplemental Indenture, the “ Indenture ”).

RECITALS

WHEREAS , the Company wishes to amend the Indenture to,

(1) waive the requirements of Section 2.01(b)(ii) of the Indenture in order to permit the issuance of additional Notes (the “ Additional Notes ”), in an amount up to $7,820,000.00, on a pro rata basis, to Noteholders who consent to this Fourth Supplemental Indenture (the “ Consenting Noteholders ”);

(2) permit the Company, at its option, until September 18, 2008 to redeem any and all outstanding Notes at the One Time Redemption Price (as defined below) and to decrease the interest rate on and after the redemption date on the outstanding Notes by 125 basis points for each $10 million dollars of Equity Sale Proceeds used to make such redemption;

(3) provide for the distribution of the proceeds from the sale of certain assets pursuant to Section 4.12 of the Indenture;

(4) permit the issuance of four (4) year warrants to Consenting Noteholders, on a pro rata basis, which enable the Consenting Noteholders to purchase up to fifteen percent (15%) of the issued and outstanding Common Stock of the Company in the aggregate;

(5) waive and amend under Section 4.16A of the Indenture relating to the Noteholders’ Refinancing and Defaulted Financing Options;

(6) waive existing financial covenants and substitute new financial covenants; and

(7) permit the Required Holders to designate two board members;

WHEREAS , in consideration for such amendments and waivers, the Company is consenting to increase the interest rate on the Notes from thirteen percent (13%) to eighteen (18%) per year (subject to reduction as set forth in paragraph 2 of the Second Allonge to Note annexed hereto) and permitting at the Noteholders’ option, one-half of the PIK interest to be paid in registered common shares of the Company at VWAP, as defined herein;

WHEREAS , Sections 8.02(a) of the Indenture provides that, with the consent of Noteholders of at least fifty percent (50%) in aggregate principal amount of the Notes (the “ Requisite Consents ”), the Company and the Trustee shall be entitled to execute supplemental indentures adding any provisions to or changing in any manner or eliminating any provision of the Indenture or any Security Document or modifying the rights of such Holders (with certain exceptions as provided in Section 8.02(b) of the Indenture not relevant to this Fourth Supplemental Indenture since each Holder affected has consented);

WHEREAS , the Company has solicited consents from Noteholders to approve the amendments to the Indenture set forth herein (the “ Proposed Amendments ”);

WHEREAS , the Company has received, in form acceptable to the Trustee, and delivered to the Trustee, the Requisite Consents to effect the Proposed Amendments under the Indenture; and

WHEREAS , all things necessary to make this Fourth Supplemental Indenture a valid agreement of the Company in accordance with its terms have been done.

NOW, THEREFORE, in consideration of the premises, it is mutually covenanted and agreed, for the equal and proportionate benefit of all Noteholders, as follows:

ARTICLE I

AUTHORIZATIONS

1.1. Effectiveness and Effect

(a) This Fourth Supplemental Indenture shall become binding upon execution and effective upon the (i) satisfaction of each of the conditions set forth in Article IV, (ii) receipt and delivery of the Requisite Consents to the Company and the Trustee, (iii) execution of this Supplemental Indenture and the Second Allonge in the form attached hereto as Exhibit A by the Company and the Trustee, (iv) issuance by the Company of the Additional Notes on a pro rata basis to the nearest $1,000 to Noteholders who consent to this Fourth Supplemental Indenture, and (v) except with the consent of holders of a majority in aggregate principal amount of the Notes, the accuracy and completeness of all statements, representations and warranties made in connection with this Fourth Supplemental Indenture or in any document delivered in connection herewith. Upon execution and delivery of this Fourth Supplemental Indenture, the Indenture shall be modified, amended and supplemented in accordance with this Fourth Supplemental Indenture, and all the terms and conditions of both shall be read together as though they constitute one instrument, except that, in the case of conflict, the provisions of this Fourth Supplemental Indenture will control. In the case of a conflict between the terms and conditions contained in the Notes and those contained in the Indenture, as modified, amended and supplemented by this Fourth Supplemental Indenture, the provisions of the Indenture, as modified, amended and supplemented by this Fourth Supplemental Indenture, shall control. Each of the Indenture, as modified, amended and supplemented by this Fourth Supplemental Indenture, and the Notes as amended by the Second Allonge are hereby ratified and confirmed, in all respects, and shall remain in full force and effect and shall bind every Noteholder.

-2-

(b) The Section headings in the Fourth Supplemental Indenture have been inserted for convenience and reference only, are not to be considered a part hereof or thereof and shall in no way modify or restrict any of the terms or provisions hereof or thereof.

(c) On and after the date hereof, all references to the Indenture in the Indenture or in any agreement, document or instrument delivered in connection therewith or pursuant thereto shall be deemed to refer to the Indenture as modified, amended and supplemented by this Fourth Supplemental Indenture.

ARTICLE II

WAIVER AND CONSENT

2.1. The Noteholders hereby waive the conditions precedent to the issuing of the additional notes in Section 2.01(b)(ii) of the Indenture and consent to the issuance pro rata (based on the principal amount of Notes held by each Consenting Noteholder on May 19, 2008 divided by $78,205,000) to the Consenting Noteholders of up to an additional $7,820,000 of Notes due 2010, so that an aggregate of up to $86,025,000 principal amount of Notes may be outstanding.

ARTICLE III

AMENDMENTS TO INDENTURE

3.1. Definitions . SECTION 1.01 of the Indenture “ Definitions ” is amended to include the following additional definitions in alphabetical order:

“ Acceptable Refinancing ” has the meaning set forth in Section 4.16A.

“ Base Compensation ” has the meaning set forth in Exhibit D.

“ China Transaction ” means net proceeds from the sale or licensing of the Company’s technology for use in China.

“ Consenting Noteholders ” has the meaning set forth in the Recitals to the Fourth Supplemental Indenture.

“ Consolidated Adjusted EBITDA ” means, for any period, an amount determined for Borrowers on a consolidated basis equal to (i) the sum, without duplication, of the amounts for such period of (a) Consolidated Net Income, plus (b) Consolidated Interest Expense, plus (c) provisions for taxes based on income, plus (d) total depreciation expense, plus (e) total amortization expense, plus (f) other non-cash items reducing Consolidated Net Income (including, without limitation, liabilities resulting from trade/barter transactions, but excluding any such non-cash item to the extent that it represents an accrual or reserve for potential Cash items in any future period or amortization of a prepaid Cash item that was paid in a prior period), less (ii) the sum, without duplication of the amounts for such period of (a) other non-cash items increasing Consolidated Net Income for such period (including, without limitation, gains resulting from trade/barter transactions, excluding any such non-cash item to the extent it represents the reversal of an accrual or reserve for potential Cash item in any prior period), plus (b) interest income, plus (c) other non operating income.

-3-

“ Disclosed Sale ” shall mean the sale for at least fifteen million dollars ($15,000,000) of the Company’s operations described in a letter to the Noteholders dated this date.

“ Fourth Supplemental Indenture ” shall mean the Fourth Supplement dated as of May 19, 2008 among the Company, the Subsidiary Guarantors named therein and the Trustee.

“ LTM EBITDA ” means the Company’s Consolidated Adjusted EBITDA calculated for the most recently ended four fiscal quarters.

“ Office Depot Litigation ” shall mean that certain litigation between the Company and Office Depot, Inc. pending in Delaware Superior Court for Kent County, Delaware.

“ One Time Redemption Price ” means the par value of the Notes, plus any and all accrued and unpaid interest on such Notes to but excluding the Redemption Date.

“ Payment Proceeds ” has the meaning set forth in Section 4.12 (b).

“ PIK Interest ” has the meaning set forth in the Second Allonge.

“ Remaining Proceeds ” has the meaning set forth in Section 4.12 (b).

“ Scanner Amount ” means an amount of money which a majority of the Board of Directors, with the consent of at least one of the Noteholder Directors, determines is necessary or desirable for the Company to use to support its program to lease or acquire scanners; provided that such amount shall not exceed $5.0 million and is permitted to be incurred (and is incurred) pursuant to Section 4.09(i).

“ Trading Day ” means (i) if the relevant stock or security is listed or admitted for trading on The New York Stock Exchange, Inc., the Nasdaq Global Market, the Nasdaq Capital Market or any other national securities exchange, a day on which such exchange is open for business; (ii) if the relevant stock or security is quoted on a system of automated dissemination of quotations of securities prices, a day on which trades may be effected through such system; or (iii) if the relevant stock or security is not listed or admitted for trading on any national securities exchange or quoted on any system of automated dissemination of quotation of securities prices, a day on which the relevant stock or security is traded in a regular way in the over-the-counter market and for which a closing bid and a closing asked price for such stock or security are available.

“ Velocity Technology Sale ” means any sale or license in a single transaction for at least ten million dollars ($10,000,000) of the Company’s technology and standard operating procedures for use outside North America.

“ VWAP ” on a Trading Day means the greater of (i) the volume weighted average price of the Common Stock for such Trading Day and the previous four days (five day VWAP) as reported by Bloomberg Financial Markets or, if Bloomberg Financial Markets is not then reporting such prices, by a comparable reporting service of national reputation selected by the Required Holders and reasonably satisfactory to the Company; and (ii) $.88, being the greater of the closing price of the Common Stock on the Trading Date on which this Agreement is executed and delivered or the Trading Date immediately prior to the date of this Agreement. If VWAP cannot be calculated for the Common Stock on such Trading Day on any of the foregoing bases, then the Company shall submit such calculation to an independent investment banking firm of

-4-

national reputation reasonably acceptable to the Noteholders, and shall cause such investment banking firm to perform such determination and notify the Company and the Investors of the results of determination no later than two (2) Business Days from the time such calculation was submitted to it by the Company. All such determinations shall be appropriately adjusted for any stock dividend, stock split or other similar transaction during such period.

3.2 “ Warrant” Definition . The definition of “ Warrant ” in Section 1.01 of the Indenture is hereby amended and restated in its entirety as follows:

“ Warrant ” or “ Warrants ” means collectively each of those certain warrants (i) originally issued to the Initial Purchasers on the Issue Date together with the Notes as comprising the Units and (ii) issued pursuant to the Fourth Supplemental Indenture.

3.3 Optional Redemption . Section 3.01 of the Indenture (“ Optional Redemptions ”) is hereby amended to add a new Section 3.01(e) as follows:

3.01(e) At any time prior to September 18, 2008, the Company may, at its option, on any one or more occasions, redeem any or all of the Notes against payment of the One-Time Redemption Price from any Equity Sale Proceeds. If the Company effects any redemption pursuant to this paragraph, the interest rate on the Notes outstanding following such redemption will be decreased on and after the redemption date by one hundred and twenty five basis points (1.25%) for each $10 million in aggregate principal amount of Notes actually redeemed pursuant to this paragraph; provided that the interest rate shall not be decreased to a rate of less than 13.0% per annum by reason of this paragraph.

3.4. Asset Sales . Section 4.12. of the Indenture (“Limitation on Asset Sales”) is hereby amended and restated in its entirety as follows:

SECTION 4.12. Limitation on Asset Sales .

Pending the final application of any such Net Proceeds, the Company may temporarily reduce the revolving Indebtedness included among the Senior Facility Obligations or otherwise invest such Net Proceeds in Cash Equivalents.

(a) Any Net Proceeds from Asset Sales (other than Velocity Technology Sale and Disclosed Sale) that are not applied or invested as provided in the first sentence of this Section, or otherwise used as a permanent reduction of the Senior Facility Obligations, will be deemed to constitute “ Excess Proceeds ”. The Company may, subject to the other terms of this Indenture, use any of the Excess Proceeds equal to or less than $1,000,000 in the aggregate, for any purpose not prohibited by the Indenture. On any date that the aggregate amount of Excess Proceeds under this Indenture exceeds one million dollars ($1,000,000) (an “Asset Sale Offer Trigger Date”), the Company will be required to make an offer to all Holders of Notes issued under this Indenture (an “Asset Sale Offer”) to purchase the maximum principal amount of Notes and, if the Company is required to do so under the terms of any other Indebtedness on a pro rata basis with the Notes that may be purchased out of the Excess Proceeds, at a purchase price in cash in an amount equal to one hundred percent (100%) of the principal amount thereof plus accrued and unpaid interest, if any, thereon, to the date of purchase in accordance with the procedures set out in this Indenture. To the extent that the aggregate amount of Notes (and any Other Indebtedness subject to such Asset Sale Offer) tendered pursuant to such Asset Sale Offer is less than the Excess Proceeds, the Company may, subject to the other terms of this Indenture,

-5-

use any remaining Excess Proceeds for any purpose not prohibited by this Indenture. If the aggregate principal amount of Notes surrendered by Holders thereof in connection with any Asset Sale Offer exceeds the amount of Excess Proceeds, the Trustee shall select the Notes to be purchased on a pro rata basis; provided that no Note shall be repurchased in part if the remaining balance thereof would be less than one thousand dollars ($1000). Upon completion of the offer to purchase made under this Indenture, the amount of Excess Proceeds that was the subject of such offer to purchase shall be reset at zero.

(b)

(i) One hundred percent (100%) of the Net Proceeds of any recovery from the Office Depot Litigation,

(ii) one hundred percent (100%) of the Net Proceeds from the first ten million dollars ($10,000,000) and seventy percent (70%) of Net Proceeds in excess of ten million dollars ($10,000,000) from any Velocity Technology Sale, and

(iii) one hundred percent (100%) of the Net Proceeds from the first ten million dollars ($10,000,000) and seventy percent (70%) of Net Proceeds in excess of ten million dollars ($10,000,000) from the Disclosed Sale, the Net Proceeds described in clauses (i) (ii) and (iii) (the “Payment Proceeds”).

shall, to the extent required by the Senior Facility Agent, be applied by the Company to permanently reduce the Senior Facility Obligations (a “ Permanent Reduction ”) with the remaining proceeds (the “ Remaining Proceeds ”) made available to the Company. The Company may, subject to the other terms of this Indenture, use any of the Remaining Proceeds for any purpose not prohibited by this Indenture (other than a Restricted Payment). If the Senior Facility Agent does not require such mandatory reduction or otherwise waives the application of any Payment Proceeds as a permanent reduction on the Senior Facility Obligations, the Company may use such Payment Proceeds for its scanner lease and purchase program (“ Scanner Use ”) in an amount not to exceed the Scanner Amounts. To the extent any Payment Proceeds are not used as a Permanent Reduction or Scanner Use, the Company shall be required to use such Payment Proceeds to make an Asset Sale Offer to all Holders of Notes issued under this Indenture to purchase the maximum principal amount of Notes and, if the Company is required to do so under the terms of any other Indebtedness on a pro rata basis with the Notes that may be purchased out of the Payment Proceeds, at a purchase price in cash in an amount equal to one hundred percent 100% of the principal amount thereof plus accrued and unpaid interest, if any, thereon, to the date of purchase in accordance with the procedures set out in this Indenture. To the extent that the aggregate amount of Notes (and any Other Indebtedness subject to such Asset Sale Offer) tendered pursuant to such Asset Sale Offer is less than the Payment Proceeds, the Company may, subject to the other terms of this Indenture, use any of the Payment Proceeds for any purpose not prohibited by this Indenture. If the aggregate principal amount of Notes surrendered by Holders thereof in connection with any Asset Sale Offer exceeds the amount of Payment Proceeds, the Trustee shall select Notes to be purchased on a pro rata basis; provided that no Note shall be repurchased in part if the remaining balance thereof would be less than $1,000. No reduction of the Senior Facility Obligations shall adversely affect the ability of the Company to borrow the Scanner Amounts subject to the conditions for such borrowing in the definition thereof.

-6-

3.5. Refinancing and Defaulted Financing Options in Favor of Holders . Section 4.16A. of the Indenture (“Refinancing and Defaulted Financing Options in Favor of Holders”) is hereby amended and restated in its entirety as follows:

SECTION 4.16A. Refinancing and Defaulted Financing Options in Favor of Holders .

The Noteholders hereby consent to any refinancing of Senior Facility Obligations provided that (a) the amount to be refinanced does not exceed $11.5 million plus the Scanner Amount, (b) the rate of interest (not including any default rate or PIK interest) does not exceed LIBOR plus 800 basis points (the “ Acceptable Refinancing ”) and (c) the final maturity date of any facility shall be the later of (i) the final maturity date of the Senior Facility Obligations or (ii) May 31, 2010. In the event Company desires to refinance the Senior Facility Obligations in a manner other than an Acceptable Refinancing, then in that event, the Company shall afford the Noteholders, by delivery of written notice to the Trustee ( the “Refinancing Notice ”) of such proposed refinancing (i) setting forth all of the material terms and conditions for such proposed refinancing; (ii) providing a reasonably detailed description of the procedures to be followed by such Holders to exercise their rights under this Section 4.16A(a) and (iii) attaching or enclosing a copy of this Section 4.16A(a), and the Holders shall have, a five (5) day period (subject to earlier termination effective immediately upon the Holders’ delivery of written notice to the Company indicating their intention not to pursue any such option) after receipt by the Holders of such notice (the “ Refinance Option Period ”) during which the Holders shall have the right to provide such refinancing to the Company on substantially the same terms and conditions and in any event on terms and conditions at least as favorable to the Company as those set forth in the Refinancing Notice. Each Noteholder who desires to participate in such refinancing shall deliver to the Company, prior to the end of the Refinance Option Period, a notice electing to participate in such refinancing and stating the maximum principal amount of such refinancing such Noteholder is willing to fund. The Holders shall not be permitted to participate in such refinancing unless the Company receives during the Refinance Option Period notices from Holders electing to fund an amount at least equal to the full amount of the refinancing described in the Refinancing Notice (a “ Qualified Notice ”) (which notice may be signed and delivered in counterparts). During the Refinance Option Period (and if the Holders deliver a Qualified Notice, thereafter until the consummation of such refinancing), the Company shall provide such cooperation and information as such Holders that have delivered the Qualified Notice, or any of them, may reasonably request in connection with their evaluation of such refinancing. If the Holders deliver a Qualified Notice, then the Holders who delivered such notice (the “ Participating Holders ”) shall enter into definitive documentation for such facility with the Company and shall be prepared to fund any such facility pursuant to the terms thereof (subject to the terms and conditions for the closing of such financing), and such financing shall be provided by the respective Participating Holders in proportion to the amount of financing or refinancing each of them committed to fund in the Qualified Notice or in such other proportion as such Holders shall agree. If the Holders fail to deliver a Qualified Notice during the Refinance Option Period, then the Company may consummate such financing or refinancing during the forty-five (45) day period after the expiration of the Refinance Option Period on the terms and conditions described to the Holders in the Refinancing Notice. If the Company does not consummate such financing or refinancing during such forty-five (45) day period or if the Company proposes to modify any material terms of such financing or refinancing, then the Company shall not consummate such financing or refinancing without again following the procedures provided in this Section 4.16A(a). The rights provided by this Section 4.16A(a) shall apply to any subsequent Obligations of the Company and/or its Restricted Subsidiaries incurred as a result of the entry into or later refinancing or replacement

-7-

of the Senior Facility Documents as referred to in the first sentence of this Section 4.16A(a), and the rights of the Holders under this Section 4.16A(a) as to any particular financing or refinancing shall not be affected by the failure of the Holders to exercise the right provided by this Section 4.16A(a) with respect to any preceding financing or refinancing.

3.6 Conditions and Limitations Regarding Senior Facility Obligations . Section 4.16(c) of the Indenture (the “Conditions and Limitations Regarding Senior Facility Obligations”) is hereby amended and restated in its entirety as follows:

(c) The Intercreditor Agreement provides that the maximum amount of Senior Facility Obligations permitted thereunder shall be permanently reduced by all amounts applied from time to time to repay principal of the Senior Facility Obligations (other than pursuant to any initial or subsequent refinancing in whole or in part), which are accompanied by a permanent reduction in the revolving credit commitment under the Senior Facility Agreement, and the Company and each Restricted Subsidiary agrees that as between the Company and the Restricted Subsidiaries, on one hand, and the Trustee and the Noteholders, on the other hand, the amount of the Senior Facility Obligations that are permitted to be incurred under Section 4.09 and Section 4.16 shall be permanently reduced by any such reduction in the maximum amount of Senior Facility Obligations permitted under the Intercreditor Agreement.

3.7. Financial Covenants . Sections 3.11, 4.21 and 4.22 of the Indenture are deleted. A new Section 4.21 “ Financial Covenants ” is added to the Indenture immediately following Section 4.20 and reads as follows:

SECTION 4.21 Financial Covenants

The Company and its Restricted Subsidiaries shall maintain the financial covenants set forth on Exhibit B annexed hereto, which are made a part of the Indenture.

3.8. Consent of Noteholders . The lead in clause to Section 8.02(b) is amended and restated as follows:

(b) However, no modification or amendment may, without the consent of a two-thirds (2/3rds) majority of the Holders of the then outstanding balance of notes affected thereby,

3.9. Warrants . A new Article 13 “ Warrants ” is added to the Indenture immediately following Article 12 and reads as follows:

ARTICLE 13 Warrants .

(a) The Company issued certain Common Stock Purchase Warrants to the Noteholders in connection with the original issuance of the Notes. The Company agrees to modify all Warrants held by Consenting Noteholders to have an exercise price of $1.35 per share and to modify anti-dilution protections for issuances based on price pursuant to the Amendment Agreement annexed hereto as Exhibit E.

(b) As additional consideration for entering into this Fourth Supplemental Indenture, the Company agrees to issue to each Consenting Noteholder its pro rata share (based on the principal amount of Notes held by each Consenting Noteholder on May 19, 2008 divided by $78,205,000) of four year Warrants to purchase 433,855 shares of the Common Stock of the Company (representing 15.0% of the issued and outstanding shares of Common Stock of the Company as of the date hereof) on the terms and in the form of Exhibit F annexed hereto.

-8-

(c) Nasdaq . The issuance and amendment of the Warrants provided for in (a) and (b) above, the issuance of the shares underlying such Warrants and the issuance of Common Stock in payment of PIK Interest under the terms of the Notes as amended by the allonge annexed hereto is subject to the filing of an additional listing application for such shares with Nasdaq. The Company will promptly file such application after the date hereof and use commercially reasonable efforts to cause such shares to be approved for listing by Nasdaq as promptly as practical. If for any reason Nasdaq does not agree to approve any or all of such shares for listing, the Company will either (i) schedule a meeting of shareholders and cause its shareholders to approve the issuance of such shares or (ii) issue to the Consenting Noteholders the shares and/or warrants to purchase shares that are approved for listing and negotiate in good faith with the Consenting Noteholders to provide them with modified or alternative consideration which has reasonably equivalent value to the shares or warrants which can not be issued without approval by the shareholders of the Company.

3.10. Directors . A new Article 14 “ Director ” is added to the Indenture immediately following Article 13 and reads as follows:

ARTICLE 14 Director .

(a) The Required Holders (the “ Director Designator ”) shall have the right to designate up to two directors (the “ Noteholder Directors ”) to be appointed to the Board promptly following such designation, and the Company shall cause such Noteholder Directors to be duly appointed or elected to the Board; provided , however , that such directors must be (a) reasonably qualified to serve as a Board member and (b) agree to and be qualified to serve as a member of the audit committee of the Board, in full compliance with all SEC and Nasdaq requirements for such service. The Company agrees not to seek to fill the current vacancy in the sixth Board seat. If the Director Designator agrees to filling the open vacancy (leaving a Board of six directors), only one of the designees need to serve and be qualified for service on the Audit Committee (but must otherwise satisfy Nasdaq and SEC standards for service and independence). Each Noteholder Director shall be provided with reasonable and customary insurance and have the benefit of customary indemnification and exculpation agreements with the Company.

(b) The Company agrees to cause (within five business days of the date that a Noteholder Director becomes a director pursuant to paragraph (a) above) one of the Noteholder Directors to be engaged as a consultant to the Company pursuant to the terms of a consulting agreement containing terms and conditions that are commercially reasonable to be mutually agreed upon by the Company and the Director Designator.

(c) In the event that either of the Noteholder Directors resigns or is removed from office, the Company agrees to take all necessary actions to install, in lieu of such person, such new person on the Board as may be designated by the Director Designator, in accordance with Section (a) above.

(d) Except for actions as may be taken by the Company’s preferred or common shareholders under existing agreements or without the consent of the Company, the Company agrees not to take any action, whether at any annual or special meeting of the Company’s stockholders or in connection with any other to increase the size of the Board from its current size of six members or reduce the size of the Board to less than two directors without the affirmative consent of the Director Designator.

-9-

(e) The Company agrees to take all actions necessary or advisable such that, the Director Designator is permitted to designate a director to the Board, at least one Noteholder Director shall be a member of each committee of the Company’s Board and the Board of each Subsidiary of the Company (and each committee thereof).

3.11. Compensation . The Company makes the undertakings in Exhibit D “ Compensation of Vincent Wasik ”.

3.12. Senior Obligations . Section 4.09(i) is amended and restated in its entirety as follows:

“the incurrence or existence of no more than $11.5 million (plus the Scanner Amount) in aggregate principal amount 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 (the “Applicable Facility Cap”), Senior Facility Obligations, less, without duplication, (i) 50% of the aggregate amount of any repayments of term Indebtedness under Senior Facility Obligations, (ii) all repayments of revolving credit Indebtedness under such Senior Facility Obligations effected with a corresponding commitment reduction under such Senior Facility Obligation, and (iii) 100% of the Net Proceeds of Asset Sales used to repay Indebtedness under Senior Facility Obligations;

3.13 Representations and Warranties . The Company makes the representations and warranties to the Company set forth in Exhibit C annexed hereto.

ARTICLE IV

CONDITIONS PRECEDENT

4.1 Conditions Precedent . The effectiveness of the amendments to the Indenture contemplated by Article III are subject to the following:

(a) delivery to the Noteholders and the Trustee of the Waiver and Eleventh Amendment in the form of Exhibit G hereto (the “ First Lien Amendment ”), duly executed by the holders of the requisite principal amount of indebtedness thereunder, and the satisfaction of all conditions to effectiveness thereunder; and

(b) delivery to the Noteholders of a Perfection Certificate in the form attached hereto as Exhibit H and continued compliance with the provisions of this Fourth Supplemental Indenture.

(c) delivery to the Trustee of (i) and Officer’s Certificate; (ii) and Opinion of Counsel; and (iii) such other documents, certificates and consents as Trustee may reasonably request pursuant to the terms of the Indenture.

-10-

ARTICLE V

MISCELLANEOUS

5.1. Counterparts . This Fourth Supplemental Indenture may be executed in several counterparts, each of which shall be an original and all of which shall constitute the same instrument.

5.2. Conflict with the Trust Indenture Act . If any provision of this Fourth Supplemental Indenture limits, qualifies or conflicts with any provision of the Trust Indenture Act (the “ TIA ”) that is required under the TIA to be part of and govern any provision of this Fourth Supplemental Indenture, the provision of the TIA shall control. If any provision of this Fourth Supplemental Indenture modifies or excludes any provision of the Fourth Supplemental Indenture that may be so modified or excluded, the provision of the TIA shall be deemed to apply to the Indenture as so modified or to be excluded by this Fourth Supplemental Indenture, as the case may be.

5.3. Successor; Benefits of Fourth Supplemental Indenture, etc . All agreements of the Company in this Fourth Supplemental Indenture shall bind their respective successors. Nothing in this Fourth Supplemental Indenture or the Notes, express or implied, shall give to any Person, other than the parties hereto and thereto and their respective successors hereunder or thereunder and the Holders of the Notes, any benefit of any legal or equitable right, remedy or claim under the Indenture, this Fourth Supplemental Indenture or the Notes.

5.4. Certain Duties and Responsibilities of the Trustee . In entering into this Fourth Supplemental Indenture, the Trustee shall be entitled to the benefit of every provision of the Indenture relating to the conduct or affecting the liability or affording protection to the Trustee, whether or not elsewhere herein so provided.

5.5. Expenses . Notwithstanding anything set forth in the Indenture to the contrary, the Company shall reimburse the Trustee for all reasonable out-of-pocket cost and expenses incurred in connection with this Fourth Supplemental Indenture.

5.6. Governing Law . The law of the State of New York shall govern and be used to construe this Fourth Supplemental Indenture.

5.7 Ratification . Except as specifically amended above, the Indenture is and shall continue to be in full force and effect and is hereby ratified and confirmed in all respects. Each Guarantor hereby acknowledges that it has read this Fourth Supplemental Indenture and consents to the terms hereof and further confirms and agrees that, notwithstanding the effectiveness of this Supplemental Indenture, its obligations under its Guarantee shall not be impaired or affected and such Guarantee is, and shall continue to be, in full force and effect and is hereby confirmed and ratified in all respects.

5.8 Further Assurances . The Company and each of its subsidiaries agree that, from time to time upon the request of the Trustee or any Noteholder, it will promptly execute and deliver such further documents and do such other acts and things as the Trustee or such Noteholder may request in order to affect the purposes of any Security Document.

[Signature page follows]

-11-

IN WITNESS WHEREOF, the parties have caused this Fourth Supplemental Indenture to be duly executed as of the date first written above.

-12-

EXHIBIT A

SECOND ALLONGE TO NOTE

Second Allonge to one in the series of the 12.0% Senior Secured Notes due 2010, dated as of July 3, 2006 (the “ Note ”) in the aggregate principal amount of $78,205,000, issued by VELOCITY EXPRESS CORPORATION. From and after the date of this Second Allonge:

1. The interest rate of the Note shall be 18% per annum effective as of the date hereof.

2. Notwithstanding the foregoing, if the Company effects a redemption of the Notes pursuant to Section 3.01(e) of the Indenture, then the interest rate on the Note shall decrease effective on and after the date of redemption, by one hundred and twenty five basis points (1.25%) for every $10 million of aggregate principal amount of Notes actually redeemed by the Company; provided that the interest rate shall not be decreased to a rate of less than 13.0%  per annum by reason of this paragraph

3. The Company will pay interest hereon (except Defaulted Interest, which shall be payable to Persons who are registered Holders on any earlier date of written demand therefore) to the Persons who are registered Holders at the close of business on May 31 or November 30 next preceding the Interest Payment Date (whether or not a Business Day). All interest payments in 2008 shall accrue and shall be paid on each Interest Payment Date by addition of such amount to the principal amount outstanding under this Note (“ PIK Interest ”). Interest payments in 2009 shall accrue and be paid 50% in cash and 50% in PIK Interest on each Interest Payment Date. All interest payments in 2010 shall accrue and be paid in cash. At the option of the Noteholder on at least five (5) business days prior written notice, fifty percent (50%) of the PIK Interest may be paid in registered shares of Common Stock the Company based on the VWAP measured as of the Interest Payment Date. The Company shall deliver such shares in payment of PIK Interest within ten (10) business days after the relevant Interest Payment Date. Holders must surrender Notes to a Paying Agent to collect principal payments. The Company will pay principal and non PIK Interest in money of the United States of America that at the time of payment is legal tender for payment of public and private debts. Non PIK Interest may be paid by check mailed to the Noteholder entitled thereto at the address indicated on the register maintained by the Registrar for the Notes. Notwithstanding the foregoing, no Holder shall be entitled to request that PIK Interest be paid in shares of Common Stock of the Company if the receipt of such shares would cause the Holder to become a beneficial owner of 19.9% or more of the Common Stock of the Company.

Dated: June 6, 2008.

-13-

EXHIBIT B

FINANCIAL COVENANTS

A. Minimum Cash .

The Company and the Subsidiary Guarantors shall maintain at all times cash and Cash Equivalents which are subject to the perfected Lien created in favor of the Trustee for the benefit of the Holders pursuant to the Security Documents (in each case, free of Liens other than (i) Security Document Liens as aforesaid, (ii) rights of setoff of the applicable depository bank or securities intermediary, and (iii) the Senior Lien as, when and to the extent applicable pursuant to the Intercreditor Agreement) of not less than $3.0 million.

B. Minimum Cash and Accounts Receivable .

The Company and the Subsidiary Guarantors shall maintain at all times cash, Cash Equivalents and Qualified Accounts Receivable which are subject to the perfected Lien created in favor of the Trustee for the benefit of the Holders pursuant to the Security Documents (in each case, free of Liens other than (i) Security Document Liens as aforesaid, (ii) rights of setoff of the applicable depository bank or securities intermediary, and (iii) the Senior Lien as, when and to the extent applicable pursuant to the Subordination Agreement) of not less than $26 million.

C. Minimum Quarterly EBITDA

The Company shall not fail to achieve LTM EBITDA, measured on a quarterly basis, of at least the required amount set forth in the following table for the applicable period set forth opposite thereto:

The Company shall deliver to the Trustee via and Officer’s Certificate and each Noteholder a detailed computation of its LTM EBITDA no later than the 30 ^th calendar day following the end of each fiscal quarter set forth above. Notwithstanding the forgoing, any Noteholder may elect by written notice to the Company to not receive such information until such information is publicly disclosed by the Company.

D. Driver Accounts Payable

The Company and its Restricted Subsidiaries shall cause all amounts due to its independent contractor drivers to be paid on a timely basis in all material respects.

-14-

EXHIBIT C

REPRESENTATIONS

The Company represents and warrants to the Consenting Noteholders as follows:

(i) The Company has been duly incorporated and is validly existing as a corporation in good standing under the laws of its jurisdiction of incorporation with corporate power and authority to own, lease and operate its properties and to conduct its business as described in the Company’s annual and periodic filings with the SEC and to execute, deliver and perform its obligations under the Fourth Supplemental Indenture. The Company has all requisite corporate power and authority to make and consummate the Consent Solicitation in accordance with their terms.

(ii) The solicitation of the Consents and the consummation of the transactions contemplated in the Indenture Supplement have been duly authorized by all necessary corporate action on the part of the Company, except to the extent that Nasdaq determines that shareholder approval is required for issuance of shares of its common stock in payment of the notes or upon issuance of the Warrants being issued or amended hereunder.

(iii) The Indenture Supplement has been duly authorized, executed and delivered by the Company. The Indenture constitutes, and the Indenture Supplement when duly authorized, executed and delivered by the trustee thereunder, will constitute, a valid and binding obligation of the Company, enforceable against the Company in accordance with its terms.

(iv) The Notes have been duly authorized by the Company and constitute valid and binding obligations of the Company entitled to the benefits of the Indenture (as amended by the Indenture Supplement), and enforceable against the Company in accordance with their terms.

(v) (A) The solicitation of the Consents, (B) the effectuation of the Indenture Supplement, (C) the execution, delivery and performance by the Company of the Indenture Supplement, and (D) the consummation by the Company of the transactions described in the Indenture Supplement and compliance with the terms herein or therein (all of the foregoing, collectively, the “ Transactions ”), in each case, (x) do not and will not result in any violation of the charter or by-laws or similar organizational documents of the Company or any of its subsidiaries, (y) do not and will not conflict with, or result in a breach or violation of any of the terms or provisions of, or constitute an event of default (or an event which with notice or lapse of time or both would become an event of default) under, or give to others any rights of termination, amendment, acceleration or cancellation of, or result in the creation or imposition of any lien, charge or encumbrance upon any property or assets of the Company or any of its subsidiaries under, (a) any contract, indenture, mortgage, lease or other agreement, known to such counsel, to which the Company or any of its subsidiaries is a party or by which any of them may be bound or to which any of its properties or assets are bound or affected or (b) any existing applicable law, rule or regulation, or any judgment, order or decree known to such counsel of any government, governmental or regulatory instrumentality or agency or court, domestic or foreign, having jurisdiction over the Company, any of its subsidiaries

-15-

or any of their properties or assets and (2) complies and will comply in all material respects with all applicable laws, rules and regulations of any government or governmental or regulatory instrumentality of agency, including, without limitation, the Exchange Act, state takeover laws and Regulations T, U and X promulgated by the Board of Governors of the Federal Reserve System.

(vi) None of the Transactions nor the execution, delivery and performance of the Indenture Supplement by the Company, and the consummation of the transactions contemplated hereby, require or will require any consent of, approval of, waiver by, license or authorization from, or permit of, or other action by or filing or registration with or notification to, any governmental or regulatory agency by the Company or any of its subsidiaries except for filings with the Securities and Exchange Commission, the Nasdaq Stock Market and any state securities filings.

(vii) To the best knowledge of the Company, no injunction, restraining order or denial of any application for approval has been issued or proceedings, litigation or investigation initiated or threatened with respect to the Transactions by or before any governmental or regulatory agency, or any court.

(viii) Assuming that each of the Noteholders is an institutional accredited investor, the securities of the Company being issued in the Transactions are not required to be registered pursuant to the Securities Act of 1933, as amended, and the rules and regulations of the Securities and Exchange Commission thereunder.

(ix) The Security Documents create a valid security interest in favor of the Trustee and the Noteholders in the Collateral in which each of the Company and its subsidiaries parties thereto has rights only as and when such rights are acquired and a valid security interest may be created under Article 9 of the New York.

(x) The Indenture Supplement does not, of itself, adversely affect the validity under the UCC of the security interest of the Trustee and the Noteholders (the “ Secured Party ”) in that part of the collateral described in the Security Agreement in which the Grantors have rights in which a valid security interest may be created under Article 9 of the UCC (the “ UCC Collateral ”) and after giving effect to the Indenture Supplement, Secured Party’s security interest in the UCC Collateral will be a valid security interest under Article 9 of the UCC to the same extent that it was a valid security interest immediately before the effectiveness of the Indenture Supplement.

(xi) The Indenture Supplement does not, of itself, adversely affect perfection of Secured Party’s security interest under the UCC in that part of the UCC Collateral in which, immediately before the effectiveness of the Indenture Supplement, Secured Party had a perfected security interest by virtue of the filing of the Financing Statement in the Office of the Secretary of State of the State of Delaware (the “ Filing Collateral ”) and after giving effect to the Indenture Supplement, Secured Party’s security interest in such Filing Collateral will be a perfected security interest under Article 9 of the UCC to the same extent that it was a perfected security interest immediately before the effectiveness of the Indenture Supplement.

-16-

(xii) For that part of the UCC Collateral that constitutes “certificated securities” within the meaning of Section 8-102(a)(4) of the UCC (“ the Pledged Securities ”), the Indenture Supplement does not, of itself, adversely affect perfection of Secured Party’s security interest under the UCC in the Pledged Securities and after giving effect to the Indenture Supplement, Secured Party’s security interest in such Pledged Securities will be a perfected security interest