Exhibit 99.1

Velocity Express Announces Third Quarter Fiscal 2009 Results

WESTPORT, Conn. May 13, 2009 — Velocity Express Corporation (NASDAQ: VEXP), the nation’s largest provider of time definite regional delivery solutions, announced operating results for its quarter ended March 28, 2009.

Highlights:

• Fourth consecutive quarter of positive Adjusted EBITDA, despite economic downturn

• Trailing 12 month Adjusted EBITDA of $6.7 million

• Gross margin of 29.4%, up 400 basis points from last year

Vincent A. Wasik, Velocity’s Chairman and Chief Executive Officer, stated, “We are pleased to have achieved our fourth consecutive quarter of positive Adjusted EBITDA despite the dramatic economic slowdown. Gross margin continued to improve from year to year and we continued to manage all other operating expenses in line with revenue.”

Financial Summary for the quarter:	Quarters Ended
($000’s)	3/28/09			12/27/08			3/29/08
Revenue	$	60,825		$	65,749		$	82,159
Gross Profit before depreciation		17,909			18,468			20,896
Gross Margin % before depreciation		29.4	%		28.1	%		25.4	%
Operating Expenses included in Adjusted EBITDA *		16,890			16,543			22,553
Adjusted EBITDA *	$	1,019		$	1,925		$	(1,657	)
Depreciation, Amortization, Non-Cash Compensation and Non-recurring Expenses for Integration, Restructuring, Litigation, Global Alliance Strategic Transaction and Debt Restructuring		2,124			1,958			2,009
Loss from Operations	$	(1,105	)	$	(33	)	$	(3,666	)

* see Exhibit B

Mr. Wasik continued, “Revenue for the quarter ended March 28, 2009 was $60.8 million compared to $65.7 million in the December quarter of 2008 and $82.2 million in the March quarter of 2008. Sequential and year over year revenue comparisons were driven by lower delivery volumes from continuing customers and lower fuel surcharge revenue because of the economic downturn and the continued migration of bank customers to the Check 21 scanning technology. In addition, our managed exit from unfavorable contracts acquired with CD&L contributed to lower revenue in the March quarter of 2009 compared to the March quarter of 2008.”

The Company reported gross profit before depreciation for the quarter of $17.9 million, or 29.4% of sales, compared to $18.5 million, or 28.1%, in the December quarter of 2008 and $20.9 million, or 25.4%, for the same quarter last year. The main reason gross margin improved is that average revenue per driver rose more rapidly than average settlement per driver, although both continue to rise.

Operating expenses included in Adjusted EBITDA were $16.9 million, or 27.8% of sales, compared to $16.5 million (25.2%) in the December quarter and $22.6 million (27.5%) in the same quarter last year. The $400,000 increase in operating expenses compared to the December quarter is entirely due to legal expenses associated with the various class action and other employee classification lawsuits we are defending.

Page 1

Adjusted EBITDA was $1.0 million compared to $1.9 million in the December 2008 quarter and a ($1.7 million) loss for the March quarter last year. The operating loss for the March quarter was $1.1 million, compared to losses of $33 thousand in the December quarter of 2008 and $3.7 million in the March 2008 quarter.

The Company’s calculation of Adjusted EBITDA for both the March and December quarters includes adjustments for expenses we are incurring for: (1) creation of the global alliance of domestic time-definite package delivery companies in other countries around the world, (2) certain non-recurring expenses associated with the May 2008 debt re-structuring and the recent replacement of our former revolving credit facility and (3) our wrongful termination litigation against a former customer. There were no such expenses in the March quarter of 2008 although that quarter did include $0.2 million of CD&L merger integration and restructuring charges.

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 improve gross margins, and if so, our ability to continue as a going concern and our ability to provide high quality cost effective outsourcing solutions. 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 be unable to fund our future capital needs and we may need funds sooner than anticipated; we may be unable to maintain driver pay at acceptable levels or improve gross margins and if so, we may be unable to continue as a going concern; we may be unable to continue to provide high quality, cost effective outsourced solutions for our customers; we may be adversely affected by the recessionary economy and our large customers could reduce or discontinue using our services; 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; we could fail to make payments or otherwise comply with the covenants in our credit agreements, including those related to EBITDA and available cash; 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 funds to do so; and the other risks identified in the section entitled “Risk Factors” in the Company’s Annual Report on Form 10-K as amended for the year ended June 28, 2008 and Quarterly Report on Form 10-Q for the quarter ended March 28, 2009 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:	Or
Velocity Express Corporation	Institutional Marketing Services (IMS)
Edward W. (Ted) Stone, CFO	John G. Nesbett/Jennifer Belodeau
203-349-4199	203-972-9200
tstone@velocityexp.com	jnesbett@institutionalms.com

Page 2

EXHIBIT A:

VELOCITY EXPRESS CORPORATION AND SUBSIDIARIES

CONDENSED CONSOLIDATED BALANCE SHEETS

(Unaudited)

(Amounts in thousands)

	March 28, 2009			June 28, 2008
ASSETS
Current assets:
Cash	$	1,837		$	4,240
Accounts receivable, net of allowance of $807 and $1,724 at March 28, 2009 and June 28, 2008, Respectively		18,902			25,126
Accounts receivable - other		1,119			815
Prepaid insurance		4,747			1,635
Other prepaid expenses and other current assets		1,071			720
Total current assets		27,676			32,536
Property and equipment, net		6,028			6,981
Goodwill		35,138			35,138
Intangible assets, net		19,733			21,333
Deferred financing costs, net		2,773			2,164
Other assets		4,014			3,797
Total assets	$	95,362		$	101,949
LIABILITIES AND SHAREHOLDERS’ DEFICIT
Current liabilities:
Trade accounts payable	$	26,752		$	26,533
Accrued wages and benefits		3,576			4,078
Accrued legal and claims		1,350			4,102
Accrued insurance and claims		2,652			3,075
Accrued interest		4,107			5,708
Related party liabilities		40			52
Other accrued liabilities		1,155			1,705
Revolving line of credit		10,020			7,942
Current portion of long-term debt		910			1,152
Total current liabilities		50,562			54,347
Long-term debt, less current portion		74,391			46,498
Accrued insurance and claims		405			538
Other long-term liabilities		4,012			4,992
Total liabilities		129,370			106,375
Commitments and contingencies
Total shareholders’ deficit		(34,008	)		(4,426	)
Total liabilities and shareholders’ deficit	$	95,362		$	101,949

Page 3

EXHIBIT A:

VELOCITY EXPRESS CORPORATION AND SUBSIDIARIES

CONSOLIDATED STATEMENTS OF OPERATIONS

FOR THE THREE MONTHS ENDED MARCH 28, 2009, DECEMBER 27, 2008, & MARCH 29, 2008

AND NINE MONTH PERIODS ENDED MARCH 28, 2009 AND MARCH 29, 2008

(Unaudited)

(Amounts in thousands, except per share data)

	Three Months Ended									Nine Months Ended
	March 28, 2009			December 27, 2008			March 29, 2008			March 28, 2009			March 29, 2008
Revenue	$	60,825		$	65,749		$	82,159		$	199,147		$	261,567
Cost of services		42,916			47,281			61,263			143,059			196,923
Depreciation		422			460			351			1,377			952
Gross profit		17,487			18,008			20,545			54,711			63,692
Operating expenses:
Occupancy		4,431			3,804			4,975			12,628			14,036
Selling, general and administrative		12,459			12,739			17,578			39,068			54,140
		16,890			16,543			22,553			51,696			68,176
Non-recurring expenses for litigation, global alliance strategic transaction / debt restructuring		961			683			—			2,087			—
Integration and restructuring charges		—			51			176			51			1,181
Depreciation, amortization, asset impairment		741			764			1,482			2,331			4,450
Total operating expenses		18,592			18,041			24,211			56,165			73,807
Loss from operations		(1,105	)		(33	)		(3,666	)		(1,454	)		(10,115	)
Other income (expense):
Interest expense, net		(10,007	)		(9,048	)		(5,018	)		(28,595	)		(14,831	)
Other (including a loss on debt extinguishment of $0.3 million in 2009)		(307	)		—			3			(314	)		4
Loss before income taxes		(11,419	)		(9,081	)		(8,681	)		(30,363	)		(24,942	)
Income taxes		3			(8	)		105			(5	)		276
Net loss	$	(11,422	)	$	(9,073	)	$	(8,786	)	$	(30,358	)	$	(25,218	)
Net loss applicable to common shareholders	$	(13,688	)	$	(11,315	)	$	(10,613	)	$	(36,805	)	$	(32,494	)
Basic and diluted net loss per share	$	(3.73	)	$	(3.36	)	$	(3.78	)	$	(10.71	)	$	(11.77	)
Weighted average common stock shares outstanding used in the basic and diluted net loss per share calculation		3,668			3,371			2,807			3,437			2,761

Page 4

EXHIBIT B: 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 and/or non-recurring 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 is also more closely correlated than other GAAP financial measures to the definition of Consolidated Cash Flow in our Indenture and the definition of EBITDA in our Revolving Credit Agreement as amended. These measures are components 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. 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 MONTHS ENDED MARCH 28, 2009, DECEMBER 27, 2008, & MARCH 29, 2008

AND NINE MONTH PERIODS ENDED MARCH 28, 2009 AND MARCH 29, 2008

(Amounts in thousands)

	Three Months Ended									Nine Months Ended
	March 28, 2009			December 27, 2008			March 29, 2008			March 28, 2009			March 29, 2008
Net loss	$	(11,422	)	$	(9,073	)	$	(8,786	)	$	(30,358	)	$	(25,218	)
Interest expense, net		10,007			9,048			5,018			28,595			14,831
Income taxes		3			(8	)		105			(5	)		276
Depreciation		630			691			1,062			2,093			3,179
Amortization of intangible assets		533			533			771			1,600			2,223
Stock based compensation		—			—			—			—			151
Other non-operating (income)/exp.		—			—			(3	)		—			(4	)
Asset impairments		—			—			—			15			—
Loss on debt extinguishment		307			—			—			314			—
Integration and restructuring costs		—			51			176			51			1,181
Non-recurring expenses for Litigation, Global Alliance Strategic Transaction / Debt Restructuring		961			683			—			2,087			—
Adjusted EBITDA	$	1,019		$	1,925		$	(1,657	)	$	4,392		$	(3,381	)

Page 5