AMENDED ANDRESTATED LOAN AND SECURITY AGREEMENT

Exhibit 10.9

Execution Copy

FIFTH AMENDMENT TO

AMENDED AND RESTATED LOAN AND SECURITY AGREEMENT

THIS FIFTH AMENDMENT TO AMENDED AND RESTATED LOAN AND SECURITY AGREEMENT (“Fifth Amendment”) is made as of December 21, 2004, by and among the borrower signatories hereto (individually a “Borrower” and collectively, “Borrowers”); the lenders who are signatories hereto (“Lenders”); and FLEET CAPITAL CORPORATION (“FCC”), a Rhode Island corporation with an office at One South Wacker Drive, Suite 3400, Chicago, Illinois 60606, as agent for Lenders hereunder (FCC, in such capacity, being “Agent”).

W I T N E S S E T H:

WHEREAS, Borrowers, Agent and Lenders entered into a certain Amended and Restated Loan and Security Agreement dated as of November 26, 2003, as amended by a certain First Amendment to Amended and Restated Loan and Security Agreement (“First Amendment”) dated as of January 26, 2004 by and among Borrowers, Agent and Lenders, by a certain Second Amendment to Amended and Restated Loan and Security Agreement (“Second Amendment”) dated as of January 31, 2004 by and among Borrowers, Agent and Lenders and by a certain Third Amendment to Amended and Restated Loan and Security Agreement (“Third Amendment”) dated as of March 31, 2004 by and among Borrowers, Agent and Lenders and by a certain Fourth Amendment to Amended and Restated Loan and Security Agreement dated as of July 1, 2004 by and among Borrowers, Agent and Lenders (said Amended and Restated Loan and Security Agreement, as so amended, is hereinafter referred to as the “Loan Agreement”); and

WHEREAS, Borrowers desire to amend and modify certain provisions of the Loan Agreement and, subject to the terms hereof, Agent and Lenders are willing to agree to such amendments and modifications;

NOW THEREFORE, in consideration of the premises, the mutual covenants and agreements herein contained, and any extension of credit heretofore, now or hereafter made by Agent and Lenders to Borrowers, the parties hereto hereby agree as follows:

1. Definitions. All capitalized terms used herein without definition shall have the meanings given to them in the Loan Agreement. The definitions of “Investors” and “Investor Note Documents” as defined in Section 9 of this Fifth Amendment are hereby added to Appendix A to the Loan Agreement:

2. Reserves. If at any time after the Fifth Amendment Effective Date (x) Borrower achieves as of the last day of any fiscal month, EBITDA for each of the three consecutive months then ended equal to or greater than $0 and achieves EBITDA for the six months then ended of $6,000,000 or more and (y) as of the last day of the fiscal month referred to in clause (x) above, average Availability for the 30 days then ended and actual Availability as of the last day of such fiscal month equals or exceeds $5,000,000, then Agent and Lenders agree to release the Availability Reserve and reduce it to $0. This Section 2 of the Fifth Amendment amends and supersedes Section 3 of the Fourth Amendment.

3. Additional Reserves; Changes in Advance Rates. During the period beginning on the Fifth Amendment Effective Date and ending on a date (the “Reserve Standstill Date”) which is the earliest of (i) the Notification Event, (ii) December 31, 2006, (iii) the failure by Borrowers to fulfill their obligations under Section 6 of the Fourth Amendment or Section 8 of the Fifth Amendment; and (iv) the occurrence of any other Event of Default, Agent and Lenders agree not to implement any new Reserves, decrease the advance rates contained in the definition of Borrowing Base, change the criteria for determining Eligible Accounts or determine Eligible Accounts in a manner inconsistent with past practice or amend the definition of Availability; provided that at all times Agent shall be entitled to create additional Reserves based on increases in the dilution ratio for Borrowers’ Accounts above 6% based on a new formula attached hereto as Exhibit A; provided, further, that Agent may implement Reserves (“Tax Reserves”) for any accrual for penalty and interest relating to delinquent tax payments prior to the date hereof, if Availability is less than $4,000,000 at any time (the “Trigger Date”) and such Tax Reserves shall be in the amount of the accrual for penalty and interest relating to such delinquent tax payments on the Trigger Date and shall be reduced, upon delivery by Borrowers of evidence of the payment or successful elimination of such penalty or interest obligations by the amount of the payment made or the eliminated obligation. This Section 3 of the Fifth Amendment amends and supersedes Section 4 of the Fourth Amendment.

4. Reaffirmation of Representations and Warranties. Borrowers hereby reaffirm each of the warranties and representations contained in the Loan Agreement and the Loan Documents as if each such representation and warranty were made on the date hereof, subject to such amendments and modifications to the Exhibits to the Loan Agreement as are attached hereto. Further Borrowers represent and warrant to Agent and Lenders that as of the date hereof there are no existing and continuing Defaults or Events of Default after giving effect to this Fifth Amendment.

5. Waiver of Certain Financial Reporting Defaults. As of the Fifth Amendment Effective Date, Agent and Lenders agree to waive any Default or Event of Default arising from the failure of Borrowers, (u) to give any notice required by subsection 8.1.2 for events occurring on or prior to the date hereof; (v) to deliver the interim financial statements and related items required by subsection 8.1.3 for periods ending on or prior to the date hereof within the time frames required by subsections 8.1.3(ii), (iii) and (iv), (w) to deliver to Agent and Lenders the audited consolidated financial statements required by subsection 8.1.3(i) and related items required by subsection 8.1.3 for the fiscal year ending July 3, 2004 on or prior to the date hereof, (x) to file with the Securities and Exchange Commission its (i) annual 10-K Report for the fiscal year ending July 3, 2004 and (ii) form 10Q for the first quarter of fiscal year 2005, in each case, within the time periods prescribed by applicable law and regulations of the Securities and Exchange Commission, (y) to deliver the Borrowing Base Certificate for periods ending on or prior to October 31, 2004 within the time periods required by subsection 8.1.4 and (z) to deliver to Agent and Lenders the Projections for the fiscal year ending nearest June 30, 2005 within the time periods prescribed in subsection 8.1.6 of the Agreement. The waivers contained in this Section 5 do not apply to any section of the Loan Agreement other than subsection 8.1.2, subsection 8.1.3, subsection 8.1.4, subsection 8.1.6 and any other covenants that are violated because of Borrowers’ breach of the foregoing specified covenants or any other periods ending after those specified in this paragraph.

2

6. Waiver of Events of Default Resulting from Peritas Transaction. Subject to the fulfillment of the conditions precedent list below, Majority Lenders shall be deemed to have consented to and waived any Default or Event of Default resulting from: (x) Borrowers advancing prior to the date hereof up to $2,200,000 to Borrowers’ Affiliate, Peritas, LLC, a Delaware limited liability Company (“Peritas”), to permit Peritas to purchase vans or other motor vehicles, which vans or other motor vehicles will be rented to independent contractors of Borrowers for use in servicing Borrowers customers; (y) Borrowers making such advances by permitting Account Debtors to offset against Accounts of Borrowers owed to Borrowers by Account Debtors the purchase price of said vans or other motor vehicles; and (z) VEI entering into a certain Agency Agreement (“Agency Agreement”) with Peritas, dated May 1, 2004 (the transactions referred to in clauses (x), (y) and (z) are hereinafter referred to as the “Peritas Transactions”). The consent contained in this Section 6 of this Fifth Amendment is subject to the fulfillment of each of the following conditions precedent:

(a) Borrowers shall have delivered to Agent true and correct executed copies of the Agency Agreement (Agent acknowledges receipt of an unsigned draft copy of an Agency Agreement), together with all amendments, exhibits and schedules thereto;

(b) Borrowers shall have delivered to Agent true and correct executed copies of the Master Purchase Agreement between Peritas and the applicable Account Debtor, together with all amendments, exhibits and schedules thereto (Agent acknowledges receipt of an unsigned draft copy of a Master Purchase Agreement);

(c) All such loans and advances from Borrowers to Peritas have been repaid on or prior to March 31, 2005.

7. Other Events of Default. As of the Fifth Amendment Effective Date, Agent and Lenders agree to waive any Default or Event of Default resulting from (v) Borrowers failing to pay accrued payroll taxes when due and incurring interest and penalties as a result of such non-payment on or prior to the date hereof; (w) Borrowers incurring on or prior to the date hereof Indebtedness to THLPV so long as such Indebtedness was converted into equity on or prior to the date hereof; (x) Borrowers failing to comply with the provisions of subsection 8.2.8 for the fiscal year ending July 3, 2004 so long as the aggregate amount of Capital Expenditures for such fiscal year (including, without limitation, by way of Capitalized Leases but excluding Capital Expenditures financed by Permitted Purchase Money Indebtedness) did not exceed Six Million Dollars ($6,000,000); (y) Borrowers failing to comply with the provisions of Section 7 of the Fourth Amendment on or prior to the date hereof; and (z) any change in Control resulting from THLPV obtaining additional Securities of Parent on or prior to the date hereof. The waivers contained in this Section 7 do not apply to any Section of the Loan Agreement other than subsection 8.2.2, subsection 8.2.8 and subsection 10.1.10 of the Loan Agreement and Section 7 of the Fourth Amendment and any other covenants that are violated because of Borrowers’ breach of the foregoing specified covenants or any other periods other than those referenced herein.

8. Conference Calls. From the Fifth Amendment Effective Date until the Termination Date, Borrowers covenant that, upon request by Agent, Borrowers’ Chief Executive Officer, Chief Financial Officer, Senior Vice President of Finance or other senior officer of

3

Borrowers acceptable to Agent, a representative of THLPV and a representative of the consultant referred to in Section 6 of the Fourth Amendment, if so requested by any Lender, shall participate in conference calls to be held every other week at times reasonably set by Agent concerning the progress of Borrowers’ GEOCOM and sales implementation and Borrowers’ business, operations and financial prospects; provided that in each case, the failure or inability of said consultant to participate in any such conference calls shall not be deemed a breach by Borrowers of this Section 8. This Section 8 of the Fifth Amendment amends and supersedes Section 7 of the Fourth Amendment.

9. Consent to Incursion of Additional Indebtedness and Granting of Permitted Liens. As of the Fifth Amendment Effective Date, Agent and Lenders hereby consent to and waive any Default or Event of Default resulting from (i) Borrowers incurring additional Indebtedness pursuant to the terms and conditions of the “Investor Note Documents” and (ii) Velocity Express Corporation and Velocity Express, Inc. granting a third subordinate Lien on their assets to “Investors” (as defined below) pursuant to the Investor Note Documents so long as such Investor Note Documents include (a) cross acceleration rights to this Agreement, but not cross default rights (other than with respect to payment defaults), and (b) an acknowledgment by the Investors that (1) their Lien is subordinate to the Lien of Agent and BET and (2) if an event of default occurs under the Investor Note Documents and Investors receive proceeds of Borrowers’ collateral prior to the repayment of the Obligations hereunder and the BET obligations, Investors will hold such proceeds in trust for Agent and BET and will deliver such proceeds first to Agent until the Obligations are paid in full and second to BET until BET’s obligations are paid in full. As used herein, “Investor Note Documents” shall mean (x) the 6% Convertible Note to be issued to Velocity Express Corporation to each “Investor” (as defined in the Purchase Agreement referred to in (y)) below dated as of December 21, 2004), (y) the Purchase Agreement by and between Velocity Express Corporation and the investor signatories thereto (“Investors”) dated as of December 21, 2004 (the “Purchase Agreement”) and (z) that certain Security Agreement by and between Velocity Express Corporation and Investors dated as of December 21, 2004. Borrowers represent and warrant that they have delivered to each Lender true and complete executed copies of the documents and agreements referred to in clauses (x), (y) and (z) of the previous sentence together with all schedules, exhibits, amendments and modifications thereto. Borrowers covenant not to prepay the Indebtedness evidenced by the Investor Note Documents prior to its stated maturity date.

10. Additional Event Default. Borrowers, Agent and Lenders agree that it shall be an Event of Default if the 6% Convertible Notes referred to in clause (x) of the definition of Investor Note Documents are not all converted in full into equity of Velocity Express Corporation on or prior to April 29, 2005.

11. Amendments to Loan Agreement.

(a) Appendix A of the Loan Agreement shall be amended by amending and restating the following definition in its entirety to read as follows:

“Notification Event – the earlier of (x) the date on which Agent receives written notice from THLPV that THLPV has elected to terminate its obligations under Section 2 of the Capital Contribution Agreement; and (z) the date on which Borrowers’ Availability

4

is $0 or less, unless as of such date (1) THLPV or third parties have agreed to make additional cash investments in Borrowers (either directly or indirectly through Parent) such that Availability is greater than or equal to $0, or (2) Borrowers shall have caused an Additional Third Party Letter of Credit, containing the terms and conditions provided for in the definition of such term and otherwise in form and substance acceptable to Majority Lenders, to be delivered to Agent, and Borrower shall have drawn down on such Additional Third Party Letter of Credit and used the proceeds thereof to repay the Revolving Credit Loans in an amount necessary to cause Availability to be equal or greater than $0.

(b) Section 10.1.3 of the Loan Agreement shall be amended and restated to read as follows until the earlier of (i) May 1, 2005 and (ii) the approval of the stockholders of the Borrowers of the Proposals (as defined in the Purchase Agreement), at which time Section 10.1.3 shall read as originally provided in the Loan Agreement:

“10.1.3 Breach of Specific Covenants. Borrowers shall fail or neglect to perform, keep or observe any covenant contained in Section or subsection 5.2, 5.3, 6.1.2, 6.2.4, 6.2.5, 8.1.8, 8.2 (other than as set forth in (b) below) or 8.3 hereof on the date that Borrowers are required to perform, keep or observe such covenant or shall fail or neglect to perform, keep or observe any covenant contained in (a) Section 8.1.4 hereof within 3 Business Days, (b) Section 8.2.1, Section 8.2.2, Section 8.2.3, Section 8.2.4 or Section 8.2.18 hereof within 10 days, (c) Section 8.1.1 hereof within 30 days, (d) Section 8.1.3 hereof within 60 days, (e) Section 8.1.2, Section 8.1.5 or Section 8.1.6 hereof within 90 days following the date on which Borrowers are required to perform, keep or observe such covenant; provided that, the grace periods provided herein shall terminate upon the earlier of (x) May 1, 2005 and (z) the approval of the stockholders of the Borrowers of the Proposals (as defined in the Purchase Agreement).”

12. BET Documents. Agent and Lenders acknowledge and agree that no Event of Default shall occur under Section 10.1.6 of the Loan Agreement as a result of Borrower not making a principal payment due on the BET Subordinated Debt on either January 31, 2005 or April 30, 2005 to the extent such payment is prohibited by Section 2.2(b) of the BET Subordination Agreement, even if BET attempts to claim that such occurrence is an “Event of Default” under the BET Documents.

13. Conditions Precedent. This Fifth Amendment shall become effective upon satisfaction of each of the following conditions precedent:

(i) Borrowers, Agent and Lenders shall have executed and delivered to each other this Fifth Amendment;

(ii) The BET Documents shall have been amended and any defaults thereunder shall have been waived, each in form and substance acceptable to Majority Lenders;

5

(iii) Borrowers shall have delivered to Agent and Lenders an unqualified opinion as it relates to going concern for audited financial statements of Parent and its Subsidiaries as of July 3, 2004 certified by Ernst & Young LLP;

(iv) Parent shall have received a new net cash equity investment or Subordinated Debt (pursuant to the Investor Note Documents) of at least $20,000,000 on or after December 1, 2004 from sources other than draws on existing letters of credit securing the Obligations. Parent, in turn, shall have invested such amount as an equity contribution in VEI and VEI shall have used the proceeds of such amount to pay down the outstanding Revolving Credit Loans, which Revolving Credit Loans may be reborrowed subject to the terms and conditions of the Loan Agreement; and

(v) THLPV shall have acknowledged that the Capital Contribution Agreement remains in full force and effect except that clause (i) of Section 11 thereof shall be modified to substitute (a) the word “earlier” for “later” where it appears therein and (b) “January 1, 2007” for “January 1, 2005.”

The date on which each of the above listed conditions precedent are satisfied is hereinafter referred to as the “Fifth Amendment Effective Date.”

14. Execution in Counterparts. This Fifth Amendment may be executed in any number of counterparts and by different parties hereto in separate counterparts, each of which shall be deemed an original but all of which together shall constitute one and the same instrument.

15. Continuing Effect. Except as otherwise specifically set out herein, the provisions of the Loan and Security Agreement shall remain in full force and effect.

16. Defaults. Agent and each Lender represents and warrants to Borrowers that it has no knowledge of any current continuing Events of Default other than those Events of Default waived pursuant to this Fifth Amendment.

17. Permitted Distributions. Agent, Lenders and BET consent to VEI or Parent making a Distribution of not more than $400,000 to THLPV (or an Affiliate thereof) on or prior to December 23, 2004 if, and only if on or after December 1, 2004 and prior to the making of such proposed Distribution, (x) THLPV or an Affiliate thereof shall have made a new cash equity investment in Parent (which in turn shall have made a comparable equity investment in VEI) or VEI, either directly or through a draw down of a new letter of credit issued for the benefit of Agent on or after the date hereof and in form and substance acceptable to Agent, in an amount equal to or greater than the proposed Distribution, and (y) a third party not under common control with THLPV has made a new cash equity investment in Parent (which, in turn, shall have made a comparable equity investment in VEI), or VEI, either directly, through a draw down of a new letter of credit issued for the benefit of Agent, or indirectly through THLPV, on or after the date hereof, in an amount equal to or greater than the proposed Distribution.

(Signature Page Follows)

6

(Signature Page to Fifth Amendment to

Amended and Restated Loan and Security Agreement)

IN WITNESS WHEREOF, this Fifth Amendment has been duly executed as of the day and year specified at the beginning hereof.

1. The undersigned hereby acknowledge and agree that the cash equity contribution described in Section 10(iv) of the foregoing Fifth Amendment shall not have the effect of reducing the amount of the Second TH Lee Letter of Credit or the Third Party Letter of Credit.

2. The undersigned consent to Borrowers, Agent and Lenders entering into the foregoing Fifth Amendment and consent and acknowledge the terms thereof.

3. The undersigned acknowledge and agree that the Capital Contribution Agreement dated as of July 1, 2004 by and between the undersigned and Fleet Capital Corporation, as agent, remains in full force and effect, except that in clause (i) of the first sentence of Section 11 of the Capital Contribution Agreement, January 1, 2007 shall be substituted for January 1, 2005. Each party hereto acknowledges and agrees that the Capital Contribution Agreement is hereby amended by (a) deleting the word “later” where it appears in Section 11 and inserting therefore the word “earlier” and (b) deleting “January 1, 2005” from clause (i) of the first sentence of Section 11 and inserting therefor “January 1, 2007”.

EXHIBIT A

The sum of dilutive credits divided by gross collections. The average calculated dilution level for the months of July, August and September, 2004 was 4.25%.