Exhibit 99.1

Velocity Express Announces Third Quarter And

Nine Months Results and CD&L Integration Status

WESTPORT, Conn. May 15, 2007 — Velocity Express, Inc. (NASDAQ: VEXP - News), the nation’s largest provider of time definite regional delivery solutions, announced third quarter and nine months results ended March 31, 2007.

Highlights since the last quarterly report include:

• Achieved on-target CD&L integration savings of $22 million in staffing, occupancy, insurance and corporate expenses.

• Awarded over $10 million in annual revenue with a number of major retailers and suppliers.

Vincent A. Wasik, Velocity’s Chairman and Chief Executive Officer, stated, “During the quarter, we continued our progress with the integration of CD&L. As of March 31, we had realized approximately $22 million of our planned acquisition related synergies and achieved our integration targets on multiple fronts, including: reduced staffing, occupancy, insurance and corporate expenses. We continue to make progress integrating the route management system in order to realize the $16 million of planned routing efficiencies in future quarters. The merging of the two companies’ databases has proven to be more challenging, and therefore has taken longer than anticipated as we have been careful to ensure that our customer deliveries are not adversely impacted. The delay is approximately 120 days and has resulted in incremental expense of $4 million in driver settlement and purchase transportation costs in the quarter. We believe the ultimate gross margin savings of $16 million are more than achievable based on our most recent April results which show an improvement of 300 basis points from the March quarter.”

Mr. Wasik continued, “As previously disclosed, the Company’s revenue declined from last year primarily due to the loss of Office Depot and the reduced revenue in the financial services sector due to the loss of certain banking customers during the merger combined with the migration of banks to the Federal Reserve Check 21 imaging technology initiative. Our research and current industry studies indicate that this trend in the financial services sector will continue at a pace that exceeds our original forecasted decline by approximately $2 million per quarter. In addition, we granted $2 million of revenue concessions to CD&L customers in the quarter as we migrated to a single database and reduced the credit terms previously extended.”

Financial Summary for the quarter:

		Mar Qtr 2007				Dec Qtr 2006				Mar Qtr 2006
Revenue		$	98,180			$	102,272			$	110,915
Gross Profit			22,102				21,949				28,637
Gross Margin			22.5	%			21.5	%			25.8	%
Operating Expense			24,226				25,865				28,435
Operating Loss			(6,245	)			(8,719	)			(1,858	)
Depreciation, Amortization, Non-Cash Comp, Integration & Transaction Fees			4,414				5,207				2,647
Adjusted EBITDA			(1,831	)			(3,511	)			789

Page 1

Ted Stone, Velocity’s Chief Financial Officer stated, “I am encouraged that our adjusted EBITDA improved sequentially from a $3.5 million loss to a $1.8 million loss, despite the additional driver settlement and purchase transportation expense, the incremental costs associated with the delay in route data compilation, and the customer concessions. I am also encouraged by recent additions to our revenue base, since in the past month we have been awarded more than $10 million of annual business with a number of major retailers and suppliers, all of which is expected to begin in the June quarter. Our bid pipeline is very robust, particularly in the retail, healthcare and office products markets. Although we are not pleased with the delay in our routing initiative which adversely impacted the March quarter results, an integration such as CD&L is complex and we continue to believe that we will be successful in completing the consolidation and reaping the rewards we expected from it when we closed the transaction.”

Mr. Wasik concluded, “Looking forward, we are keenly focused on expanding our business by diversifying our customer base and converting the expanded pipeline to drive revenue across our improving cost structure. Although we are behind in our route optimization, we believe that the June quarter will show significant progress. Finally, our increased scale domestically has opened up various strategic opportunities to leverage this leadership position and expand our business internationally.”

On August 17, 2006, Velocity acquired CD&L, creating the largest time-critical logistics company in North America. For comparative purposes, the financial data for the quarter ended March 31, 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 and separate 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 ended March 31, 2006 as they were reported at that time.

Third Quarter Results

Revenue

Third quarter revenue was $98.2 million compared to $102.3 million in the second quarter of fiscal 2007 and to pro forma revenue of $110.9 million in the third quarter of last year. Revenue declined due to the previously disclosed loss of Office Depot and the reduced revenue in the financial service sector due to the loss of certain banking customers, combined with the migration of a number of banks to the Federal Reserve Check 21 imaging technology initiative, and a slight economic slowdown in the current period.

Gross profit

The Company reported gross profit for the quarter of $22.1 million, or 22.5% of sales, compared to $21.9 million, or 21.5% of sales, in the second quarter of fiscal 2007 and to pro forma gross profit of $28.6 million, or 25.8% of sales, for the same quarter last year. The sequential improvement reflects reduced insurance, vehicle and other costs realized in the CD&L integration. Because of the delay in compiling the routing data, the related cost savings have not yet been realized. The year-to-year decline reflects the temporarily increased costs to maintain high customer service levels while simultaneously executing the longer and more costly than expected migration of CD&L’s route management system into Velocity’s. Gross margins are expected to continue to improve for the remainder of fiscal and calendar 2007.

Operating expenses

Operating expenses (occupancy and SG&A) for the quarter were $24.2 million, or 24.7% of sales, compared to $25.8 million, or 25.3% of sales, in the second quarter of fiscal 2007 and to pro forma operating expenses of $28.4 million, or 25.6% of sales, in the third quarter last year. The decrease in operating expense reflects the realization of post-acquisition integration savings.

Transaction, restructuring and integration charges for the third quarter were $2.4 million, compared to $3.0 million in the second quarter and $0 in the prior year period.

Interest expense and payment terms

Page 2

Net interest expense of $4.6 million in the quarter was up slightly from $4.4 million the December quarter and from $4.2 million on a pro forma basis in the prior year quarter due to lower interest income on excess cash balances. In the March quarter, interest expense consisted of $0.5 million in non-cash amortization of the deferred financing fees incurred with the sale of the Company’s 12% Senior Secured Notes, $1.9 million of non-cash accretion of the debt discount associated with the issuance of Warrants as part of the Notes sale, and an accrual $2.2 million for cash interest. Cash payments on the Notes will begin on June 30, 2007.

Adjusted EBITDA and Net Loss

Adjusted EBITDA for the third quarter was a loss of $1.8 million, compared to an adjusted EBITDA loss of $3.5 million in the second quarter of fiscal 2007 and pro forma Adjusted EBITDA of $0.9 million in the third quarter last year. Adjusted EBITDA improved sequentially due to improved gross margins and reduced operating expenses. Adjusted EBITDA is lower than the prior year quarter because of the margin loss associated with Office Depot and financial services customers and higher cost of delivery services required for the field integration, partly offset by reduced SG&A expenses as described above. 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 third quarter ended March 31, 2007 was $11.0 million compared to a $13.4 million in the second quarter of fiscal 2007 and to a pro forma loss of $6.2 million in the third quarter last year. Net loss attributable to common shareholders for the quarter was $13.3 million, or $0.49 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.

Nine Month Results

Revenue

Nine month revenue was $311.5 million compared to pro forma revenue of $328.1 million for the same nine month period of last year. Revenue declined due to the previously disclosed loss of Office Depot and the reduced revenue in the financial service sector due to the loss of certain banking customers, combined with the migration of a number of banks to the Federal Reserve Check 21 imaging technology initiative.

Gross Profit

The Company reported gross profit for the nine months of $71.6 million, or 23.0% of sales, compared to pro forma gross profit of $84.3 million, or 25.7% of sales, for the same nine month period last year. Lower gross profit margin reflects the temporary costs associated with maintaining high customer service levels while simultaneously completing the integration of CD&L’s field operations and route management system.

Operating expenses

Operating expenses (occupancy and SG&A) for the nine months were $77.1 million, or 24.7% of sales, compared to pro forma operating expenses of $83.7 million, or 25.5% of sales, in the same nine month period last year. The decrease in operating expense is a function of the post-acquisition integration savings.

Adjusted EBITDA and Net Loss

Adjusted EBITDA for the nine month period was a loss of $4.5 million, compared to pro forma Adjusted EBITDA of $1.6 million in the same nine months of last year. Adjusted EBITDA is lower than the prior year period because of the margin loss associated with lower revenue and higher cost of delivery services in the third quarter required for the field integration, partly offset by reduced SG&A expenses as described above.

Page 3

Velocity’s Chief Financial Officer, Edward W. (Ted) Stone, stated, “While we spent more time and money integrating the CD&L customer and route management databases than we had expected, we made considerable progress during the quarter. We achieved the targeted operating expense savings from the acquisition and integration of CD&L and we expect they will stay at approximately these levels going forward. We are also confident that we have established the route information platform needed to realize the route optimization and purchased transportation savings we set out to achieve. As we now begin to add revenue, we are confident we are well positioned for long term profitable growth.”

Conference Call

Velocity will host a conference call and webcast on Wednesday, May 16 at 9:00 a.m. EST to discuss the company’s third quarter results. To access the live webcast and slide presentation, log onto the Velocity Express website at www.velocityexpress.com and click on “Investor Info/Stock Information”. The webcast can also be accessed at www.InvestorCalendar.com. 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 replay of the webcast can be viewed 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 1-866-245-6755 and international callers may dial 1-416-915-1035. Callers should use passcode 962929.

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. 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 not be successful in integrating CD&L and 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, 2006 and its Quarterly Report on Form 10-Q for the quarter ended March 31, 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

Page 4

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

203-972-9200

jnesbett@institutionalms.com

Page 5

EXHIBIT A:

VELOCITY EXPRESS CORPORATION AND SUBSIDIARIES

CONSOLIDATED BALANCE SHEETS

(Unaudited)

(Amounts in thousands, except par value)

		March 31, 2007			July 1, 2006
ASSETS
Current assets:
Cash		$	8,958		$	1,715
Accounts receivable, net of allowance of $2,913 and $3,273 at March 31, 2007 and July 1, 2006, respectively			33,004			14,789
Accounts receivable - other			1,395			1,031
Prepaid workers’ compensation and auto liability insurance			4,408			1,932
Other prepaid expenses and other current assets			1,960			1,167
Total current assets			49,725			20,634
Property and equipment, net			9,199			6,581
Assets held for sale			589			973
						—
Goodwill			72,922			42,830
Intangible assets			28,420			—
Deferred financing costs, net			6,432			1,763
Other assets			2,277			2,872
Total assets		$	169,564		$	75,653
LIABILITIES AND SHAREHOLDERS’ EQUITY
Current liabilities:
Trade accounts payable		$	23,258		$	16,900
Accrued wages and benefits			4,995			2,755
Accrued legal and claims			6,120			4,688
Accrued insurance and claims			2,967			1,802
Accrued interest			3,229			270
Related party liabilities			—			1,430
Other accrued liabilities			3,317			977
Revolving line of credit			5,400			—
Current portion of long-term debt			865			1,363
Total current liabilities			50,151			30,185
Long-term debt, less current portion			53,695			26,185
Accrued insurance and claims			2,178			2,540
Restructuring liabilities			100			111
Other long-term liabilities			4,720			1,563
Commitments and contingencies

Page 6

Shareholders’ equity:
Preferred stock, $0.004 par value, 299,515 shares authorized 12,838 and 10,321 shares issued and outstanding at March 31, 2007 and July 1, 2006, respectively			70,426				33,243
Common stock, $0.004 par value, 700,000 shares authorized 28,331 and 16,965 shares issued and outstanding at March 31, 2007 and July 1, 2006, respectively			113				68
Stock subscription receivable			(43	)			(7,543	)
Additional paid-in-capital			371,490				313,489
Accumulated deficit			(383,259	)			(324,200	)
Accumulated other comprehensive income (loss)			(7	)			12
Total shareholders’ equity			58,720				15,069
Total liabilities and shareholders’ equity		$	169,564			$	75,653

Page 7

EXHIBIT A:

VELOCITY EXPRESS CORPORATION AND SUBSIDIARIES

CONSOLIDATED STATEMENTS OF OPERATIONS

(Unaudited)

(Amounts in thousands, except per share data)

		Three Months Ended								Nine Months Ended
		March 31,				April 1,				March 31,				April 1,
		2007				2006				2007				2006
Revenue		$	98,180			$	50,476			$	311,546			$	152,338
Cost of services			75,999				35,965				239,792				109,202
Depreciation			79				58				155				169
Gross profit			22,102				14,453				71,599				42,967
Operating expenses:
Occupancy			4,423				3,145				13,431				9,174
Selling, general and administrative			19,803				12,102				63,650				37,854
Restructuring charges and asset impairments			975				—				2,880				—
Transaction and integration costs			1,458				—				5,444				—
Depreciation and amortization			1,688				1,036				5,591				3,137
Total operating expenses			28,347				16,283				90,996				50,165
Loss from operations			(6,245	)			(1,830	)			(19,397	)			(7,198	)
Other income (expense):
Interest expense, net			(4,630	)			(1,168	)			(15,256	)			(3,511	)
Other			(116	)			(177	)			(130	)			472
Loss before income taxes and minority interest			(10,991	)			(3,175	)			(34,783	)			(10,237	)
Income taxes			22				1				37				1
Minority interest			—				—				367				—
Net loss		$	(11,013	)		$	(3,176	)		$	(35,187	)		$	(10,238	)
Net loss applicable to common shareholders		$	(13,345	)		$	(3,915	)		$	(59,800	)		$	(16,128	)
Basic and diluted net loss per share		$	(0.49	)		$	(0.23	)		$	(2.42	)		$	(1.04	)
Weighted average common stock shares outstanding used in the basic and diluted net loss per share calculation			27,330				16,699				24,696				15,581

Page 8

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 NINE MONTHS ENDED MARCH 31, 2007 AND APRIL 1, 2006

(Amounts in thousands, except per share data)

		Three Months Ended								Nine Months Ended
		March 31, 2007				April 1, 2006				March 31, 2007				April 1, 2006
	Revenue								$				98,180						$	110,915			$	311,546			$	328,099
Cost of services			75,999				82,214				239,792				243,590
Depreciation			79				64				155				190
Gross profit			22,102				28,637				71,599				84,319
Operating expenses:
Occupancy			4,423				5,103				13,431				14,649
Selling, general and administrative			19,803				23,332				63,650				69,008
Restructuring charges and asset impairments			975				—				2,880				—
Transaction and integration costs			1,458				—				5,444				—
Depreciation and amortization			1,688				2,060				5,591				6,298
Total operating expenses			28,347				30,495				90,996				89,955
Loss from operations			(6,245	)			(1,856	)			(19,397	)			(5,636	)
Other income (expense):
Interest expense, net			(4,630	)			(4,198	)			(15,256	)			(15,274	)
Other			(116	)			(177	)			(130	)			471
Loss before income taxes			(10,991	)			(6,231	)			(34,783	)			(20,439	)
Income taxes			22				22				37				37
Minority interest			—				—				—				—
Net loss		$	(11,013	)		$	(6,253	)		$	(34,820	)		$	(20,476	)
Net loss applicable to common shareholders		$	(13,345	)		$	(7,873	)		$	(59,433	)		$	(43,045	)
Basic and diluted net loss per share		$	(0.49	)		$	(0.40	)		$	(2.41	)		$	(2.33	)
Weighted average common stock shares outstanding used in the basic and diluted net loss per share calculation			27,330				19,628				24,696				18,508

Page 9

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 MONTHS AND NINE MONTHS ENDED MARCH 31, 2007 AND APRIL 1, 2006

		Three Months Ended
		March 31, 2007				April 1, 2006				Pro Forma April 1, 2006
Net loss		$	(11,013	)		$	(3,176	)		$	(6,253	)
Interest Income/Expense			4,630				1,168				4,196
Income Taxes			22				1				22
Depreciation			975				1,094				1,329
Amortization of Intangible Assets			792				—				795
Stock Based Compensation			214				523				523
Other non-operating (income)/expense			116				177				177
Transaction / Restructuring / Integration / Redundant			2,433				—				—
Minority Interest in CD&L			—				—				—
Adjusted EBITDA		$	(1,831	)		$	(213	)		$	789

Page 10

		Nine Months Ended
		March 31, 2007				April 1, 2006				Pro Forma April 1, 2006
Net loss		$	(35,187	)		$	(10,238	)		$	(20,476	)
Interest Income/Expense			15,256				3,511				15,274
Income Taxes			37				1				37
Depreciation			3,367				3,306				4,106
Amortization of Intangible Assets			2,379				—				2,382
Stock Based Compensation			808				734				734
Other non-operating (income)/expense			130				(472	)			(471	)
Transaction / Restructuring / Integration / Redundant			8,324				—				—
Minority Interest in CD&L			367				—				—
Adjusted EBITDA		$	(4,519	)		$	(3,158	)		$	1,586

Page 11