Exhibit 99.1

Velocity Express Announces Fourth Quarter And

Year End Results

WESTPORT, Conn. October 15, 2007 — Velocity Express Corporation (NASDAQ: VEXP - News), the nation’s largest provider of time definite regional delivery solutions, announced operating results for its fourth quarter and fiscal year ended June 30, 2007.

Highlights:

• Positive adjusted EBITDA in quarter ended June 30, 2007

• Gross margin improved while average driver settlement increased through route engineering

• $18 million in annualized new revenue started in September quarter of fiscal 2008, more than offsetting $15 million in lost revenue from terminated unfavorable contracts assumed with the CD&L acquisition

• Three new franchise agreements signed in September quarter of fiscal 2008

Vincent A. Wasik, Velocity’s Chairman and Chief Executive Officer, stated, “During the quarter we achieved a positive adjusted EBITDA, reflecting the considerable progress we have made with our acquisition of CD&L. We have realized all of the $22 million in acquisition synergies we had anticipated and, with a significant effort, aided by Alvarez & Marsal, we have been able to migrate all of our customer and route management information to a single database and operating system. The Company can now apply our unique route management systems to capture the full $16 million of routing efficiencies we had anticipated when we merged with CD&L. During the quarter, we saw the first benefits of the integrated databases as our route management and route engineering systems allowed us to improve driver pay by 370 basis points in the June quarter compared to the March quarter, while increasing the average settlement paid to our independent contractor drivers.”

Financial Summary for the quarter:

		June Qtr 2007				March Qtr 2007				June Qtr 2006 Pro forma
Revenue		$	98,556			$	98,180			$	112,003
Gross Profit			26,445				22,102				28,382
Gross Margin			26.8	%			22.5	%			25.3	%
Operating Expenses Included in Adjusted EBITDA *			23,735				24,012				31,737
Adjusted EBITDA *			2,793				(1,831	)			(3,421	)
Depreciation, Amortization, Non-Cash Compensation, Integration & Transaction Expenses			2,975				4,414				2,559
Operating Loss			(182	)			(6,245	)			(5,914	)

* see Exhibit C

Mr. Wasik continued, “Revenue in the June quarter benefited from new business starts with an annual value of $11 million in the first six months of calendar 2007 and future quarters will benefit from additional $18 million in annualized new starts in the September quarter. As discussed in previous communications, we reorganized our sales team earlier this year to better serve our current customer base, deepen our penetration into the vertical markets for office products, healthcare and critical parts, and expand into the retail replenishment vertical. As a result, our customer bid pipeline increased to $201 million on October 15 from $147 million on May 15 even after converting more than $20 million of the May pipeline into started new

Page 1

business. We are seeing particular interest in the retail and pharmaceutical verticals where Fortune 1000 customers clearly see the benefits of our sophisticated track-and-trace and route management technology across our integrated network of 150 same-day, time-critical, ground delivery service areas across the country.”

Over time, Velocity expects growth in these areas will more than offset the decline anticipated in the Company’s financial services business due to the migration of banks to the Federal Reserve Check 21 imaging technology initiative. Revenue from financial services has already declined from $21 million for Velocity and CD&L combined in the pre-merger June quarter of 2006 to $13.5 million in the September quarter of 2007. With the previously announced revenue reduction from Velocity’s largest financial services customer, the Company expects revenue from this vertical market will decline by another $3.3 million per quarter between the first and third quarters of fiscal 2008. In addition, Velocity has exited from other unfavorable legacy-CD&L customer contracts with annual revenues of $15 million in the automotive, financial services and healthcare verticals after failing to renegotiate these contracts to acceptable market terms.

Finally, Velocity has launched a new franchise strategy to expand its technology-driven service capability into additional areas that enhance and increase service coverage. To date, Velocity has signed franchisees in Fargo, ND; Columbus, OH; St. Louis, MO and Kansas City, MO and expects to sign two more cities before the end of October. The Company expects these first 6 franchisees to provide more than $5 million of service for Velocity customers on an annual basis, from which Velocity will record the franchise fee income. Furthermore, Velocity expects to expand its franchise program into three or four additional geographies each quarter, equivalent to $15-20 million annual value of service for Velocity customers by June 2008. Beyond the benefit to customers, franchising also allows Velocity to use capital more efficiently by eliminating the expenditures needed to open new markets while earning franchise fees that assure “day one” profitability comparable to a mature direct operation.

Ted Stone, Velocity’s Chief Financial Officer stated, “As part of our year end close, we quantified and recorded the impact of the unfavorable customer contracts mentioned above along with other adjustments primarily relating to purchase accounting. These entries had the net effect of increasing our reported earnings by approximately $1.6 million in the quarter. Even excluding these items, Adjusted EBITDA was positive as expected.”

“In view of the realized and projected declines in financial services and other revenue mentioned above, we approached our revolving credit lender shortly after the fiscal year-end to revise the Minimum EBITDA covenant of the Credit Agreement. On October 15, we entered into an amended Credit Agreement under which the lender agreed to waive our non-compliance with the Minimum EBITDA covenant for July and August 2007 and establish new covenants from September 2007 through December 2008. We are satisfied with the revised terms and confident we can continue to drive the long-term profitability of the business.”

Financial Overview

On August 17, 2006, Velocity acquired CD&L, creating the largest time-critical logistics company in the United States. For comparative purposes, the financial data for the quarter and fiscal year ended July 1, 2006 discussed below and presented in Exhibit B to this press release were prepared on a pro forma basis as if the acquisition had been consummated on July 3, 2005. The presentation also separates nonrecurring expenses associated with the acquisition, integration and restructuring of CD&L. Exhibit A to this press release provides a comparison to the actual GAAP results for the quarter and year ended July 1, 2006 as they were reported at that time.

Fourth Quarter Results

Revenue

Fourth quarter revenue was $98.6 million compared to $98.2 million in the third quarter of fiscal 2007 and pro forma revenue of $112.0 million in the fourth quarter of last year. Revenue declined from 2006 due to the previously disclosed loss of Office Depot ($7 million), the above-described declines in financial services

Page 2

revenue ($7 million), $3 million per quarter in merger-related customer losses, and a slight economic slowdown in the current period. These losses were partly offset by $2.5 million in revenue from new business starts with new and existing customers in the March and June quarters and $1.5 million from the amortization into revenue of an unfavorable contract. Revenue increased from the March quarter because new business starts and the unfavorable contract amortization exceeded the decline in financial services revenue during the quarter.

Gross profit

The Company reported gross profit for the quarter of $26.4 million, or 26.8% of sales, compared to $22.1 million, or 22.5% of sales, in the third quarter of fiscal 2007 and to pro forma gross profit of $28.4 million, or 25.3% of sales, for the same quarter last year. The sequential improvement reflects reduced total driver pay as a result of the improved driver pay management and route engineering made possible by the integrated customer and route management databases, a net benefit from the year-end purchase accounting adjustments cited earlier plus merger integration savings partly offset by cargo claims paid under unfavorable legacy CD&L contracts and new spending on our system-wide scanner upgrade. The scanner expense is part of a much larger investment we are making in partnership with our independent contractor drivers.

Operating expenses

Operating expenses (occupancy and SG&A) for the quarter were $23.7 million, or 24.1% of sales, compared to $24.0 million, or 24.5% of sales, in the third quarter of fiscal 2007 and to pro forma operating expenses of $31.9 million, or 28.4% of sales, in the fourth quarter last year. The decrease in operating expense reflects the realization of post-acquisition integration savings partly offset by legal expenses associated with the resolution of a pre-2004 contract dispute.

Net interest expense of $5.0 million in the quarter was up from $4.6 million the March quarter due to greater borrowing under the Company’s revolving credit facility. Interest expense was down from $5.6 million on a pro forma basis in the prior year quarter.

Adjusted EBITDA and Net Loss

Adjusted EBITDA for the fourth quarter was $2.8 million, compared to an Adjusted EBITDA loss of $1.8 million in the third quarter of fiscal 2007 and a pro forma Adjusted EBITDA loss of $3.4 million in the fourth quarter last year. Adjusted EBITDA improved sequentially due to improved gross margins and reduced operating expenses. Adjusted EBITDA is a non-GAAP financial measure as defined by the SEC. For a description of the reasons the Company uses this measure and a reconciliation of Adjusted EBITDA to its nearest GAAP equivalent, please see Exhibit C to this press release.

Net loss for the fourth quarter ended June 30, 2007 was $4.3 million compared to a $11.0 million in the third quarter of fiscal 2007 and to a pro forma loss of $11.7 million in the fourth quarter last year. Net loss attributable to common shareholders for the quarter was $6.2 million, or $0.20 per fully diluted share. The difference between net loss and net loss attributable to common shareholders is the result of the non-cash beneficial conversion and pay-in-kind features of our preferred stock, dominantly driven by the issuance of the Series Q preferred stock as part of the financing for the CD&L acquisition.

Conference Call

Velocity will host a conference call on Tuesday, October 16 at 9:00 a.m. ET to discuss the company’s fourth quarter results. To participate in the call by phone, dial 866-585-6398 approximately five minutes prior to the scheduled start time. International callers please dial 416-849-9626. A webcast will be available at www.velocityexpress.com as well as at www.InvestorCalendar.com. A replay of the webcast can be heard by visiting the investor relations section of the Velocity Express website. A replay of the teleconference will be available for 14 days after the call and may be accessed domestically by dialing 866-245-6755 and international callers may dial 416-915-1035. Callers should use passcode 203645.

Page 3

About Velocity Express

Velocity Express has one of the largest time definite nationwide delivery networks, providing a national footprint for customers desiring same day service throughout the United States. The Company’s services are supported by a customer-focused technology infrastructure, providing customers with the reliability and information they need to manage their transportation and logistics systems, including a proprietary package tracking system that enables customers to view the status of any package via a flexible web reporting system.

Forward Looking Statements

Certain statements in this press release, and other written or oral statements made by or on behalf of the Company, may constitute “forward-looking statements” within the meaning of the federal securities laws. Statements regarding future events and developments and the Company’s future performance that are not historical facts, as well as management’s expectations, beliefs, plans, objectives, assumptions and projections about future events or future performance, are forward looking statements within the meaning of these laws. Forward-looking statements include statements that are preceded by, followed by, or include words such as “believes,” “expects,” “anticipates,” “plans,” “estimates,” “intends,” or similar expressions and include statements about our ability to realize routing efficiencies and control driver pay, our ability to generate revenues and profits from potential customers in our pipeline, our ability to be successful with our new franchise strategy and our ability to comply with the new financial covenants in our revolving credit facility. Forward-looking statements are only predictions and are not guarantees of performance. These statements are based on beliefs and assumptions of the Company’s management, which in turn are based on currently available information. These assumptions could prove inaccurate. Forward-looking statements are also affected by known and unknown risks that may cause the actual results of the Company to differ materially from any future results expressed or implied by such forward-looking statements. Many of these risks are beyond the ability of the Company to control or predict. Such factors include, but are not limited to, the following: we may never achieve or sustain profitability; we may fail to achieve the expected cost savings from the CD&L acquisition, including due to the challenges of combining the two companies, reducing overlapping functions, retaining key employees and other related risks; we may be unable to fund our future capital needs, and we may need funds sooner than anticipated; our large customers could reduce or discontinue using our services; we may be unable to successfully compete in our markets; we could be exposed to litigation stemming from the accidents or other activities of our drivers; we could be required to pay withholding taxes and extend employee benefits to our independent contractors; risk relating to maintaining the financing under our credit agreement; we have a substantial amount of debt and preferred stock outstanding, and our ability to operate and financial flexibility are limited by the agreements governing our debt and preferred stock; we may be required to redeem our debt at a time when we do not have the proceeds to do so; and the other risks identified in the section entitled “Risk Factors” in the Company’s Annual Report on Form 10-K for the year ended June 30, 2007, as well as in the other documents that the Company files from time to time with the Securities and Exchange Commission. Management believes that the forward-looking statements contained in this release are reasonable; however, undue reliance should not be placed on any forward-looking statements contained herein, which are based on current expectations. Further, forward-looking statements speak only as of the date they are made, and management undertakes no obligation to publicly update any of them in light of new information or future events.

Contact:

Velocity Express Corporation

Edward W. (Ted) Stone,

203-349-4199

tstone@velocityexp.com

or

Institutional Marketing Services (IMS)

John G. Nesbett/Jennifer Belodeau

203-972-9200

jnesbett@institutionalms.com

Page 4

EXHIBIT A:

VELOCITY EXPRESS CORPORATION AND SUBSIDIARIES

CONSOLIDATED BALANCE SHEETS

(Amounts in thousands, except par value)

		June 30, 2007				July 1, 2006
ASSETS
Current assets:
Cash		$	14,418			$	1,715
Accounts receivable, net of allowance of $3,277 and $3,273 at June 30, 2007 and July 1, 2006, respectively			32,597				14,789
Accounts receivable - other			1,250				1,031
Prepaid workers’ compensation and auto liability insurance			3,404				1,932
Other prepaid expenses and other current assets			1,031				1,167
Total current assets			52,700				20,634
Property and equipment, net			8,457				6,581
Assets held for sale			101				973
							—
Goodwill			81,791				42,830
Intangible assets			24,327				—
Deferred financing costs, net			6,246				1,763
Other assets			2,888				2,872
Total assets		$	176,510			$	75,653
LIABILITIES AND SHAREHOLDERS’ EQUITY
Current liabilities:
Trade accounts payable		$	28,413			$	16,900
Accrued wages and benefits			3,643				2,755
Accrued legal and claims			5,854				4,688
Accrued insurance and claims			3,697				1,802
Accrued interest			5,867				270
Related party liabilities			574				1,430
Other accrued liabilities			3,383				977
Revolving line of credit			7,467				—
Current portion of long-term debt			558				1,363
Total current liabilities			59,456				30,185
Long-term debt, less current portion			55,510				26,185
Accrued insurance and claims			1,882				2,540
Restructuring liabilities			—				111
Other long-term liabilities			4,018				1,563
Commitments and contingencies
Shareholders’ equity:
Preferred stock, $0.004 par value, 299,515 shares authorized 12,239 and 10,321 shares issued and outstanding at June 30, 2007 and July 1, 2006, respectively			68,902				33,243
Common stock, $0.004 par value, 700,000 shares authorized 32,820 and 16,965 shares issued and outstanding at June 30, 2007 and July 1, 2006, respectively			131				68
Stock subscription receivable			—				(7,543	)
Additional paid-in-capital			376,041				313,489
Accumulated deficit			(389,497	)			(324,200	)
Accumulated other comprehensive income (loss)			67				12
Total shareholders’ equity			55,644				15,069
Total liabilities and shareholders’ equity		$	176,510			$	75,653

Page 5

EXHIBIT A:

VELOCITY EXPRESS CORPORATION AND SUBSIDIARIES

CONSOLIDATED STATEMENTS OF OPERATIONS

(Unaudited)

(Amounts in thousands, except per share data)

		Three Months Ended								Years Ended
		June 30, 2007				July 1, 2006				June 30, 2007				July 1, 2006
Revenue		$	98,556			$	50,092			$	410,102			$	202,430
Cost of services			72,028				36,146				311,820				145,348
Depreciation			83				54				238				223
Gross profit			26,445				13,892				98,044				56,859
Operating expenses:
Occupancy			4,424				2,836				17,855				12,010
Selling, general and administrative			18,964				13,807				82,614				51,661
			23,388				16,643				100,469				63,671
Restructuring charges and asset impairments			518				378				3,398				378
Transaction and integration costs			1,121				—				6,565				—
Depreciation and amortization			1,600				888				7,191				4,025
Total operating expenses			26,277				17,909				117,623				68,074
Loss from operations			(182	)			(4,017	)			(19,579	)			(11,215	)
Other income (expense):
Interest expense, net			(5,001	)			(1,607	)			(20,257	)			(5,118	)
Other			838				(177	)			708				295
Loss before income taxes and minority interest			(4,345	)			(5,801	)			(39,128	)			(16,038	)
Income taxes			—				(1	)			37				—
Minority interest			—				—				367				—
Net loss		$	(4,345	)		$	(5,800	)		$	(39,532	)		$	(16,038	)
Net loss applicable to common shareholders		$	(6,198	)		$	(7,519	)		$	(65,991	)		$	(23,647	)
Basic and diluted net loss per share		$	(0.20	)		$	(0.44	)		$	(2.53	)		$	(1.49	)
Weighted average common stock shares outstanding used in the basic and diluted net loss per share calculation			30,252				16,965				26,085				15,907

Page 6

EXHIBIT B:

The pro forma combined Statement of Operations that follows reflects the combination of Velocity and CD&L as if the acquisition had been completed at the beginning of the respective period. It has been prepared in accordance with Regulation S-X of the SEC but it is not accompanied by the consolidation worksheet and explanatory footnotes required under Regulation S-X. The Company’s Form 8-K/A filing on October 25, 2006 contains the required consolidation worksheet and footnotes for the year ended July 1, 2006 which are generally indicative of the pro forma adjustments reflected in the pro forma combined Statement of Operations that follows.

VELOCITY EXPRESS CORPORATION AND SUBSIDIARIES

PRO FORMA COMBINED STATEMENTS OF OPERATIONS

FOR THE THREE MONTHS AND YEARS ENDED JUNE 30, 2007 AND JULY 1, 2006

(Unaudited)

(Amounts in thousands, except per share data)

		Three Months Ended								Years Ended
		June 30, 2007				July 1, 2006				June 30, 2007				July 1, 2006
Revenue		$	98,556			$	112,003			$	410,102			$	440,102
Cost of services			72,028				83,561				311,820				327,151
Depreciation			83				60				238				250
Gross profit			26,445				28,382				98,044				112,701
Operating expenses:
Occupancy			4,424				4,756				17,855				19,405
Selling, general and administrative			18,964				27,233				82,614				96,241
			23,388				31,863				23,388				115,646
Restructuring charges and asset impairments			518				378				3,398				378
Transaction and integration costs			1,121				—				6,565				—
Depreciation and amortization			1,600				1,929				7,191				8,227
Total operating expenses			26,627				34,296				117,623				124,251
Loss from operations			(182	)			(5,914	)			(19,579	)			(11,550	)
Other income (expense):
Interest expense, net			(5,001	)			(5,625	)			(20,257	)			(20,899	)
Other			838				(177	)			708				294
Loss before income taxes			(4,345	)			(11,716	)			(39,128	)			(32,155	)
Income taxes			—				—				37				—
Minority interest			—				—				367				—
Net loss		$	(4,345	)		$	(11,716	)		$	(39,532	)		$	(32,155	)
Net loss applicable to common shareholders		$	(6,198	)		$	(15,208	)		$	(65,991	)		$	(58,253	)
Basic and diluted net loss per share		$	(0.20	)		$	(0.76	)		$	(2.53	)		$	(3.09	)
Weighted average common stock shares outstanding used in the basic and diluted net loss per share calculation			30,252				19,891				26,085				18,854

Page 7

EXHIBIT C: USE OF NON-GAAP FINANCIAL MEASURES

This press release includes disclosures regarding “Adjusted EBITDA”, which is a non-GAAP financial measure. Adjusted EBITDA, is comprised of historical EBITDA, as adjusted for certain non-cash expenses. EBITDA is defined as net earnings (loss) before interest expenses, income taxes, depreciation and amortization on an historical basis. We believe net income (loss) is the most directly comparable financial measure to EBITDA under GAAP.

We present Adjusted EBITDA for several reasons. Management believes Adjusted EBITDA is useful as a means to evaluate our ability to fund our estimated uses of cash, including the payment of interest on our debt. In addition, we have presented Adjusted EBITDA to investors in the past because it is frequently used by investors, securities analysts and other interested parties in the evaluation of companies in our industry, and management believes presenting it here provides a measure of consistency in our financial reporting. Adjusted EBITDA (also referred to in our Indenture as Consolidated Cash Flow and in our Revolving Credit Agreement as EBITDA) is also a component of the restrictive covenants and financial ratios contained in the agreement(s) governing our debt that require us to maintain compliance with these covenants and limit certain activities, such as our ability to incur additional debt and to pay dividends. The definitions in these covenants and ratios are based on Adjusted EBITDA. As a result, management believes the presentation of Adjusted EBITDA provides important additional information to investors.

While we use Adjusted EBITDA in managing and analyzing our business and financial condition and believe it is useful to our management and investors for the reasons described above, it has certain shortcomings. In particular, Adjusted EBITDA does not represent the residual cash flows available for discretionary expenditures, since items such as debt repayment and interest payments are not deducted from such measure. Accordingly, it should not be construed as an alternative to net cash from operating or investing activities, cash flows from operations or net income (loss) as defined by GAAP and is not, on its own, necessarily indicative of cash available to fund our cash needs as determined in accordance with GAAP. In addition, not all companies use identical calculations of Adjusted EBITDA, and our calculation of Adjusted EBITDA may not be comparable to Adjusted EBITDA or other similarly titled measures of other companies.

A reconciliation of the differences between Adjusted EBITDA and the most directly comparable financial measure presented in accordance with GAAP is included in the table that follows.

Reconciliation of Non-GAAP Financial Measures

VELOCITY EXPRESS CORPORATION AND SUBSIDIARIES

for the Three Month Periods Ended June 30, 2007, March 31, 2007 and July 1, 2006

		Three Month Periods Ended
		June 30, 2007				March 31, 2007				July 1, 2006				Pro Forma July 1, 2006
Net loss		$	(4,345	)		$	(11,013	)		$	(5,800	)		$	(11,716	)
Interest Income/Expense			5,001				4,630				1,607				5,625
Income Taxes			—				22				(1	)			—
Depreciation			889				975				942				1,196
Amortization of Intangible Assets			794				792				—				793
Stock Based Compensation			(347	)			214				126				126
Other non-operating (income)/expense			(838	)			116				177				177
Transaction / Restructuring / Integration / Redundant Expenses			1,639				2,433				378				378
Minority Interest in CD&L			—								—				—
Adjusted EBITDA		$	2,793			$	(1,831	)		$	(2,571	)		$	(3,421	)

Page 8

Reconciliation of Non-GAAP Financial Measures

VELOCITY EXPRESS CORPORATION AND SUBSIDIARIES

for the Years Ended June 30, 2007 and July 1, 2006

		Years Ended
		June 30, 2007				July 1, 2006				Pro Forma July 1, 2006 *
Net loss
Interest Income/Expense		$	(39,532	)		$	(16,038	)		$	(32,155	)
Income Taxes			20,257				5,118				20,899
Depreciation			37				—				—
Amortization of Intangible Assets			4,256				4,248				5,304
Stock Based Compensation			3,173				—				3,173
Other non-operating (income)/expense			461				860				860
Transaction / Restructuring / Integration / Redundant Expenses			(708	)			(295	)			(294	)
Minority Interest in CD&L			9,963				378				378
Adjusted EBITDA			367				—				—
		$	(1,726	)		$	(5,729	)		$	(1,835	)

Page 9