THIRTEENTH AMENDMENT AND WAIVER

Exhibit 10.38

THIRTEENTH AMENDMENT AND WAIVER

THIRTEENTH AMENDMENT AND WAIVER (this “Agreement”), dated as of February 17, 2009, to the Credit Agreement, dated as of December 22, 2006 (as amended, restated, supplemented or otherwise modified from time to time, including all schedules thereto, the “Credit Agreement”), by and among the lenders identified on the signature pages thereof (such lenders, together with their respective successors and permitted assigns, are referred to hereinafter each individually as a “Lender” and collectively as the “Lenders”), Wells Fargo Foothill, Inc., a California corporation, as the arranger and administrative agent for the Lenders (in such capacity, together with its successors and assigns in such capacity, the “Agent”), Velocity Express Corporation, a Delaware corporation (the “Parent”), each of the Parent’s Subsidiaries identified on the signature pages thereof as a Borrower (such Subsidiaries are referred to hereinafter each individually as a “Borrower”, and individually and collectively, jointly and severally, as the “Borrowers”), and each of Parent’s Subsidiaries identified on the signature pages thereof as a Guarantor (such Subsidiaries, together with the Parent, are referred to hereinafter each individually as a “Guarantor”, and individually and collectively, jointly and severally, as the “Guarantors”). Capitalized terms used in this Agreement and not defined herein shall have the applicable meanings given to such terms in the Credit Agreement.

WITNESSETH:

WHEREAS, one or more Events of Default have occurred and are continuing under Section 7.2(a) of the Credit Agreement as a result of the noncompliance by the Parent and its Subsidiaries with (a) the minimum EBITDA covenant set forth in Section 6.16(a) of the Credit Agreement for (i) the six (6) month period ending October 31, 2008, (ii) the seven (7) month period ending November 30, 2008, and (iii) the eight (8) month period ending on December 31, 2008, and (b) the driver pay covenant set forth in Section 6.16(c) of the Credit Agreement for the three week periods ending October 17, 2008, November 14, 2008 and December 12, 2008 (collectively, the “Specified Defaults”).

WHEREAS, the Borrowers have requested that the Agent and the Required Lenders agree and, subject to the terms and conditions of this Agreement, the Agent and the Required Lenders have agreed to waive the Specified Defaults commencing on the Amendment Effective Date (as defined below).

NOW, THEREFORE, the Agent, the Required Lenders and the Loan Parties hereby agree as follows:

1. Loan Parties Acknowledgments. The Loan Parties hereby acknowledge, confirm and agree that:

(a) As of the close of business on February 13, 2009, (i) the aggregate outstanding principal amount of the Advances (not including amounts accrued but not yet charged to the Loan Account) is $6,125,939.29 and the aggregate stated amount of all outstanding Letters of Credit is $2,694,891.00, and (ii) the Borrowers are unconditionally

indebted and liable for the repayment in full of the outstanding principal amount of all Advances, all contingent reimbursement obligations with respect to outstanding Letters of Credit and all other Obligations, including, without limitation, the Applicable Prepayment Premium, the fees set forth in the Fee Letter and the reasonable out of pocket fees and expenses of legal counsel to the Agent, without offset, defense or counterclaim of any kind, nature or description.

(b) All Obligations are secured by valid, enforceable and perfected first priority Liens (except as otherwise expressly provided in the Loan Documents) in all of the Collateral, which Liens are enforceable without offset, defense or counterclaim.

(c) (i) Each of the Loan Documents to which the Loan Parties are a party has been duly executed and delivered to the Agent and each is in full force and effect as of the date hereof, (ii) the agreements and obligations of the Loan Parties contained in the Loan Documents to which they are a party constitute the legal, valid and binding obligations of the Loan Parties, enforceable against them in accordance with their terms, and the Loan Parties have no offset, defense or counterclaim to the enforcement of such Obligations, and (iii) the Agent and the other members of the Lender Group are and shall be entitled to the rights, remedies and benefits provided for in the Loan Documents, subject to the terms of this Agreement.

(d) The Agent’s and the Lenders’ execution of this Agreement shall not constitute a novation, refinancing, discharge, extinguishment or refunding nor is it to be construed as a release, waiver or modification of any of the terms, conditions, representations, warranties, covenants, rights or remedies set forth in the Credit Agreement or any of the other Loan Documents, except as expressly provided herein.

(e) (i) Neither the Loan Parties nor any of their Subsidiaries or Affiliates has any claim or cause of action against the Agent, any Agent-Related Person, any Lender or any Lender-Related Person (or any of the directors, officers, employees, agents, Affiliates or attorneys of the foregoing), and (ii) the Lender Group has heretofore properly performed and satisfied in a timely manner all of its obligations to the Loan Parties and all of their Subsidiaries and Affiliates (if any) under the Credit Agreement and the other Loan Documents. Notwithstanding the foregoing, Loan Parties wish (and the Agent and Lenders agree) to eliminate any possibility that any past conditions, acts, omissions, events or circumstances would impair or otherwise adversely affect the Agent or any Lenders’ rights, interests, security and/or remedies under the Credit Agreement and the other Loan Documents. Accordingly, for and in consideration of the agreements contained in this Agreement and other good and valuable consideration, the Loan Parties for themselves and their Affiliates and the successors, assigns, heirs and representatives of each of the foregoing) (collectively, the “Releasors”) does hereby fully, finally, unconditionally and irrevocably release, waive and forever discharge the Agent, any Agent-Related Person, any Lender or any Lender-Related Person, together with their respective successors, assigns, subsidiaries, affiliates, agents and attorneys (collectively, the “Released Parties”) from: (x) any and all liabilities, obligations, duties, responsibilities, promises or indebtedness of any kind of the Released Parties to the Releasors or any of them and (y) all claims, demands, disputes, offsets, causes of action (whether at law or equity), suits or defenses of any kind whatsoever (if any), which the Releasors or any of them had from the beginning of the world, now has or might hereafter have against the Released Parties or any of them, in either case of clauses (x) or (y) on account of any condition, act,

2

omission, event, contract, liability, obligation, indebtedness, claim, cause of action, defense, circumstance or matter of any kind (1) that existed, arose or occurred at any time from the beginning of the world to the execution of this Agreement or (2) that could hereafter arise as a result, directly or indirectly, of the execution of (or the observance of the terms of) this Agreement, the Credit Agreement or any of the other Loan Documents. For purposes of the release contained in this clause (e), any reference to any Releasor shall mean and include, as applicable, such Person’s successors and assigns, including, without limitation, any receiver, trustee or debtor-in-possession, acting on behalf of such Person. As to each and every claim released hereunder, the Loan Parties hereby represent that they have received the advice of legal counsel with regard to the releases contained herein and agrees that no such common law or statutory rule or principle shall affect the validity or scope or any other aspect of such release.

2. Amendment. The Loan Parties, the Lenders and the Agent wish to amend the Credit Agreement. Accordingly, on the Amendment Effective Date, the parties hereto hereby agree as follows:

(a) Section 6.16 of the Credit Agreement is hereby amended by adding the following new subsection (d) to read as follows:

“(d) Liquidity Test. At all times during the period from (i) February 17, 2009 through and including February 27, 2009, the Loan Parties shall have at least $2,400,000 of Excess Availability plus Qualified Cash and (ii) February 28, 2009 and at all times thereafter, the Loan Parties shall have at least $2,700,000 of Excess Availability plus Qualified Cash.”

3. Waiver.

(a) Pursuant to the request of the Loan Parties and in accordance with Section 14.1 of the Credit Agreement, the Agent and Required Lenders hereby waive the Specified Defaults.

(b) The waiver in this Section 3 shall be effective only for the Specified Defaults and does not allow for any other or further departure from the terms and conditions of the Credit Agreement or any other Loan Document, which terms and conditions shall otherwise continue in full force and effect.

4. No Waiver; Reservation of Rights. The Agent and the Lenders have not waived, are not by this Agreement waiving, and have no present intention of waiving any Events of Default (other than the Specified Defaults) which may be continuing on the date hereof or any Events of Default which may occur after the date hereof (whether the same or similar to the Specified Defaults or otherwise), and nothing contained herein shall be deemed or constitute any such waiver. The Lender Group reserves the right, in its discretion, to exercise any or all rights or remedies under the Credit Agreement, the other Loan Documents, applicable law and otherwise (including, without limitation, any rights afforded to the Agent and Lenders under the Intercreditor Agreement) as a result of any other Events of Default that may be continuing on the date hereof or any Events of Default that may occur after the date hereof, and the Agent and the Lenders have not waived any of such rights or remedies and nothing in this Agreement, and no delay on the Agent’s and the Lenders’ part in exercising such rights or remedies, should be

3

construed as a waiver of any such rights or remedies. Each member of the Lender Group reserves the right to request any additional information (financial or otherwise) with respect to the Specified Defaults or any other Event of Default or otherwise.

5. Reaffirmation of Guaranty; Agreement as Loan Document. Except as specifically set forth in this Agreement, the Credit Agreement and the other Loan Documents (including, without limitation, the terms of any guaranty or grant of security set forth therein) shall remain in full force and effect and are hereby ratified and confirmed. Upon the effectiveness of this Agreement, each reference to the Credit Agreement in any Loan Document shall mean and be a reference to the Credit Agreement as modified hereby. This Agreement shall constitute a Loan Document and shall (unless expressly indicated herein or therein) be construed, administered, and applied, in accordance with all of the terms and provisions of the Credit Agreement and the other Loan Documents. Accordingly, it shall be an Event of Default under the Credit Agreement if (i) any representation or warranty made by the Loan Parties under or in connection with this Agreement shall have been untrue, false or misleading when made, or (ii) the Loan Parties shall fail to perform or observe any term, covenant or agreement contained in this Agreement.

6. Conditions to Effectiveness. This Agreement shall become effective and be deemed effective as of the date when, and only when, all of the following conditions have been satisfied as determined in the Agent’s sole and absolute discretion (the date of such effectiveness being herein called the “Amendment Effective Date”):

(a) The Agent shall have received a copy of this Agreement duly executed by the Borrower, the Agent and the Required Lenders;

(b) The Agent shall have received a copy of an additional Trademark Security Agreement duly executed by Velocity Express, Inc., a Delaware corporation, and acknowledged by the Agent;

(c) The Borrowers shall have paid to the Agent, for its sole and separate account, a non-refundable waiver fee equal to $50,000, in immediately available funds, in Dollars, which fee shall be earned in full when paid, provided that, the Agent may in its sole discretion charge such fee to the Loan Account pursuant to Section 2.10 of the Credit Agreement;

(d) Pursuant to Section 2.11(b)(ii) of the Credit Agreement, the Borrowers shall have paid to the Agent, for its sole and separate account, the unpaid portion of the Eleventh Amendment Fee in an amount equal to $250,000, in immediately available funds, in Dollars, provided that, the Agent may in its sole discretion charge such unpaid portion of the Eleventh Amendment Fee to the Loan Account pursuant to Section 2.10 of the Credit Agreement;

(e) The Agent shall have received from the Parent executed documents evidencing that at least sixty-six and two thirds percent (66.67%) of the Noteholders have consented to and adopted the proposed amendments to the Indenture, described in the Solicitation of Consents Relating to the $78,205,000 in the aggregate principal amount of 12% Senior Secured Notes due 2010 of Velocity Express Corporation, in the form attached hereto as Annex A (the “Consent Solicitation”)

4

(f) All reasonable out-of-pocket expenses incurred by any member of the Lender Group which have been invoiced in connection with this Agreement, the Credit Agreement or any other Loan Document, or the transactions contemplated by any of the foregoing, shall have been paid by the Borrower; and

(g) As of the Amendment Effective Date, the representations and warranties set forth in Section 7 hereof shall be true and correct.

7. Representation and Warranties. In order to induce the Agent and the Lenders to enter into his Agreement, the Loan Parties hereby represent and warrant that:

(a) At and as of the date of this Agreement and as of the Amendment Effective Date, and both prior to and after giving effect to this Agreement, no Default or Event of Default (other than the Specified Defaults) shall have occurred and be continuing or shall result from the execution of this Agreement.

(b) At and as of the date of this Agreement and at and as of the Amendment Effective Date and after giving effect to this Agreement, each of the representations and warranties contained in the Credit Agreement and the other Loan Documents is true and correct in all material respects (except to the extent that such representations and warranties relate solely to an earlier date).

(c) Each Loan Party (i) has all requisite corporate power and authority to execute and deliver this Agreement and to consummate the transactions contemplated hereby and (ii) has taken all action, corporate or otherwise, necessary to authorize the execution and delivery of this Agreement.

(d) The execution, delivery and performance by the Loan Parties of this Agreement will not (i) violate any provision of federal, state, or local law or regulation applicable to any Loan Party, the Governing Documents of any Loan Party, or any order, judgment, or decree of any court or other Governmental Authority binding on any Loan Party, (ii) conflict with, result in a breach of, or constitute (with due notice or lapse of time or both) a default under any material contractual obligation of any Loan Party, (iii) result in or require the creation or imposition of any Lien of any nature whatsoever upon any properties or assets of any Loan Party, or (iv) require any unobtained approval of any Loan Party’s interestholders or any unobtained approval or consent of any Person under any material contractual obligation of any Loan Party.

(e) This Agreement has been duly executed and delivered by each Loan Party and constitutes the legal, valid and binding obligation of the Loan Parties, enforceable against the Loan Parties in accordance with its terms, except as such enforceability may be limited by (i) applicable bankruptcy, insolvency, reorganization, moratorium or other similar laws, now or hereafter in effect, relating to or affecting the enforcement of creditors’ rights generally, and (ii) the application of general principles of equity (regardless of whether such enforceability is considered in a proceeding in equity or at law).

5

8. Lender Group Expenses. All reasonable out of pocket fees, costs and expenses incurred by any member of the Lender Group in connection with this Agreement and each of the other documents, instruments and agreements executed in connection herewith, including, but not limited to, such fees, costs and expenses incurred in connection with the negotiation, drafting, implementation and enforcement of this Agreement, shall constitute Lender Group Expenses and shall be paid in accordance with the terms hereof and the other Loan Documents.

9. Severability. The provisions of this Agreement are severable, and if any clause or provision shall be held invalid or unenforceable in whole or in part in any jurisdiction, then such invalidity or unenforceability shall affect only such clause or provision, or part thereof, in such jurisdiction and shall not in any manner affect such clause or provision in any other jurisdiction, or any other clause or provision in this Agreement in any jurisdiction.

10. Counterparts. This Agreement may be executed in any number of counterparts, each of which counterparts when executed and delivered shall be an original, but all of which shall together constitute one and the same instrument. Delivery of an executed counterpart of this Agreement by telefacsimile or other electronic transmission shall be equally effective as delivery of a manually executed counterpart.

11. Integration. This Agreement contains the entire understanding of the parties hereto with regard to the subject matter contained herein. This Agreement supersedes all prior or contemporaneous negotiations, promises, covenants, agreements and representations of every nature whatsoever with respect to the matters referred to in this Agreement, all of which have become merged and finally integrated into this Agreement. Each of the parties understands that in the event of any subsequent litigation, controversy or dispute concerning any of the terms, conditions or provisions of this Agreement, no party shall be entitled to offer or introduce into evidence any oral promises or oral agreements between the parties relating to the subject matter of this Agreement not included or referred to herein and not reflected by a writing included or referred to herein. Any single or partial exercise of any right under this Agreement shall not preclude other or further exercise thereof or the exercise of any other right, and no waiver, amendment or other variation of the terms, conditions or provisions of this Agreement whatsoever shall be valid unless in writing signed by the Agent and the Required Lenders (or any other Person whose consent is required pursuant to the terms of the Loan Documents), and then only to the extent in such writing specifically set forth. All remedies contained in this Agreement or by law afforded shall be cumulative and all shall be available to the members of the Lender Group until the Obligations have been paid in full. The failure of any party to enforce at any time any provision of this Agreement shall not be construed to be a waiver of such provisions, nor in any way to affect the validity of this Agreement or any part hereof or the right of such party thereafter to enforce each and every such provision. No waiver of any breach of this Agreement shall be held to constitute a waiver of any other or subsequent breach.

12. Binding Effect; Assignment. This Agreement shall be binding upon and inure to the benefit of the Loan Parties, the Lenders and the Agent and each of their respective successors and assigns.

6

13. Headings. Section headings in this Agreement are included herein for convenience of reference only and shall not constitute a part of this Agreement for any other purpose.

14. Governing Law; Waiver of Jury Trial. Without limiting the applicability of any other provision of the Credit Agreement or any other Loan Document, the terms and provisions set forth in Section 12 of the Credit Agreement (Choice of Law and Venue; Jury Trial Waiver) are expressly incorporated herein by reference.

[Remainder of page intentionally left blank.]

7

IN WITNESS WHEREOF, this Agreement has been duly executed as of the date first above written.

Thirteenth Amendment and Waiver

Thirteenth Amendment and Waiver

Thirteenth Amendment and Waiver

Annex A

Consent Solicitation

[To be attached]