Exhibit 99.1

VELOCITY EXPRESS ANNOUNCES FIRST QUARTER REVENUE OF $111 MILLION

Company Is On Track to Realize $39 Million in Merger Related Cost Savings

WESTPORT, Conn.—November 21, 2006—Velocity Express, Inc. (NASDAQ: VEXP), the nation’s largest provider of time definite regional delivery solutions, announced $111.1 million in revenue for the first quarter ended September 30, 2006, reflecting its acquisition of CD&L in the quarter.

The acquisition, announced on July 3 and consummated on August 17, 2006, made Velocity the largest time-critical logistics company in North America, with annual pro forma revenues of more than $440 million and 5,500 independent contractor drivers, operating from 150 locations in leading markets across the United States and Canada. Because Velocity controlled a majority of CD&L’s voting shares on July 3, 2006, CD&L’s results have been consolidated from July 3.

For comparative purposes, the figures for the quarter ended October 1, 2005 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. Exhibit A to this press release provides non-consolidated, GAAP-compliant results for the quarter ended October 1, 2005. For a more complete discussion of Velocity’s actual results for the quarter, see the Quarterly Report on Form 10-Q for the quarter ended September 30, 2006, which was filed previously.

First quarter revenue of $111 million increased 1% from pro forma revenue of $109.7 million in the first quarter last year. The Company reported gross profit for the quarter of $27.5 million, or 24.8% of sales, compared to pro forma gross profit of $27.7 million, or 25.2% of sales for the same quarter last year. While CD&L had lower gross margins than Velocity at the time of acquisition, the Company is in the process of reducing cost of delivery by utilizing a more efficient route structure across the combined company with its proprietary route optimization software and by converting legacy CD&L employee drivers to independent contractors.

Total operating expenses for the quarter were $32.0 million, or 28.8% of sales, compared to pro forma total operating expenses of $29.8 million, or 27.2% of sales in the first quarter last year. The increase in operating expense is attributable to $2.9 million in restructuring, integration, and other acquisition related items and $0.8 million of amortization of intangible assets related to CD&L’s customer list and certain non-compete contracts.

Adjusted EBITDA for the first quarter was $0.8 million, an improvement of $0.8 million compared to breakeven pro forma adjusted EBITDA in the first quarter last year. 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.

The net loss for the first quarter ended September 30, 2006 was $10.8 million compared to a pro forma loss of $8.4 million in the first quarter last year. The increased net loss is attributable to $2.9 million in restructuring, integration and other acquisition-related items and $0.8 million of amortization of intangible assets as noted above, partly offset by $1.3 million in lower expenses this year for bad debt and telecommunication services. Net loss attributable to common shareholders for the quarter was $30.9 million, or $1.42 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 CD&L merger financing.

Mr. Vincent A. Wasik, Velocity’s Chairman and Chief Executive Officer, stated, “The integration is proceeding well and we are very pleased with the positive Adjusted EBITDA of the combined companies. Our sales team was fully integrated on day one and key accounts have been transitioned appropriately. We are seeing an increased number of sales leads resulting from our expanded capabilities and scale. To date, we have successfully consolidated 30 facilities representing more than one-third of our 90 facilities targeted for combination and expect to be completed by December of this year. We have

realized approximately a third of our targeted staffing reductions. We have also made tremendous progress on conversion to our centrally managed routing and billing system and, to date, 85% of the former CD&L drivers are converting to the Velocity independent driver contract. Finally, we completed a consolidated management reporting program and expect to complete our accounting system transition in the March 2007 quarter when the last of our field locations are expected to complete their migration to Velocity’s operating systems.”

Velocity’s Chief Financial Officer, Edward W. (Ted) Stone, stated, “I am encouraged that, in a quarter where we completed a major acquisition and began a complete integration, we have not lost our momentum and have already been able to demonstrate improved revenue and Adjusted EBITDA compared to our pro forma combined results for the first quarter last year. The acquisition of CD&L was planned as the logical next step in the turnaround of Velocity that began two years ago and we believe our first quarter results demonstrate continuing progress in executing that plan.”

Velocity will host a conference call and webcast on Tuesday, November 21 at 9:00 a.m. EST to discuss the company’s first quarter results. The conference call may be accessed in the U.S. and Canada by dialing toll-free 1-866-585-6398 and international callers may access the call by dialing 1-416-849-9626. 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 must enter passcode number 909378. To access the live webcast, log onto the Velocity Express website at http://www.velocityexpress.com and click on “Stock Information/Links”. The webcast can also be accessed at http://www.InvestorCalendar.com. An online replay will be available shortly after the call.

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.

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; 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 Quarterly Report on Form 10-Q for the quarter ended September 30, 2006, 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, Inc.

Edward W. (Ted) Stone, 203-349-4199

tstone@velocityexp.com

or

Steven S. Anreder, 212-532-3232

steven.anreder@anreder.com

EXHIBIT A:

VELOCITY EXPRESS CORPORATION AND SUBSIDIARIES

CONSOLIDATED BALANCE SHEETS

(Unaudited)

(Amounts in thousands, except par value)

		September 30, 2006				July 1, 2006
ASSETS
Current assets:
Cash		$	9,754			$	1,715
Accounts receivable, net of allowance of $3,968 and $3,273 at September 30, 2006 and July 1, 2006, respectively			41,569				14,789
Accounts receivable - other			567				1,031
Prepaid workers’ compensation and auto liability insurance			8,898				1,932
Other prepaid expenses and other current assets			1,837				1,167
Total current assets			62,625				20,634
Property and equipment, net			8,648				6,581
Assets held for sale			1,136				973
Goodwill			70,845				42,830
Intangible assets			30,007				—
Deferred financing costs, net			6,829				1,763
Other assets			2,200				2,872
Total assets		$	182,290			$	75,653
LIABILITIES AND SHAREHOLDERS’ EQUITY
Current liabilities:
Trade accounts payable		$	18,534			$	16,900
Accrued insurance and claims			4,428				1,802
Accrued wages and benefits			7,059				2,755
Accrued legal and claims			6,662				4,688
Related party liabilities			—				1,430
Other accrued liabilities			8,146				1,247
Current portion of long-term debt			1,857				1,363
Total current liabilities			46,686				30,185
Long-term debt, less current portion			48,867				26,185
Accrued insurance and claims			2,742				2,540
Restructuring liabilities			53				111
Other long-term liabilities			1,522				1,563
Commitments and contingencies
Shareholders’ equity:
Preferred stock, $0.004 par value, 299,515 shares authorized 13,998 and 10,321 shares issued and outstanding at September 30, 2006 and July 1, 2006, respectively			75,983				33,243
Common stock, $0.004 par value, 700,000 shares authorized 23,702 and 16,965 shares issued and outstanding at September 30, 2006 and July 1, 2006, respectively			95				68
Stock subscription receivable			(43	)			(7,543	)
Additional paid-in-capital			361,461				313,489
Accumulated deficit			(355,090	)			(324,200	)
Accumulated other comprehensive income			14				12
Total shareholders’ equity			82,420				15,069
Total liabilities and shareholders’ equity		$	182,290			$	75,653

EXHIBIT A:

VELOCITY EXPRESS CORPORATION AND SUBSIDIARIES

CONSOLIDATED STATEMENTS OF OPERATIONS

(Unaudited)

(Amounts in thousands, except per share data)

		Three Months Ended
		September 30, 2006				October 1, 2005
Revenue		$	111,094			$	52,546
Cost of services			83,546				38,212
Gross profit			27,547				14,334
Operating expenses:
Occupancy			4,732				2,939
Selling, general and administrative			26,076				14,309
Restructuring charges and asset impairments			1,173				—
Total operating expenses			31,981				17,248
Loss from operations			(4,434	)			(2,914	)
Other income (expense):
Interest expense			(6,174	)			(1,096	)
Other			180				513
Loss before income taxes and minority interest			(10,427	)			(3,497	)
Income taxes			9				—
Minority interest			367				—
Net loss		$	(10,803	)		$	(3,497	)
Net loss applicable to common shareholders		$	(30,890	)		$	(6,577	)
Basic and diluted net loss per share		$	(1.42	)		$	(0.47	)
Weighted average common stock shares outstanding used in the basic and diluted net loss per share calculation			21,830				14,139

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 QUARTERS ENDED SEPTEMBER 30, 2006 AND OCTOBER 1, 2005

(Unaudited)

(Amounts in thousands, except per share data)

		Three Months Ended
		September 30, 2006				October 1, 2005
Revenue		$	111,094			$	109,681
Cost of services			83,546				81,999
Gross profit			27,547				27,682
Operating expenses:
Occupancy			4,732				4,708
Selling, general and administrative			26,076				25,112
Restructuring charges and asset impairments			1,173				—
Total operating expenses			31,981				29,820
Loss from operations			(4,434	)			(2,138	)
Other income (expense):
Interest expense			(6,174	)			(6,733	)
Other			180				513
Loss before income taxes			(10,427	)			(8,358	)
Income taxes			9				—
							—
Net loss		$	(10,436	)		$	(8,358	)
Net loss applicable to common shareholders		$	(30,522	)		$	(11,438	)
Basic and diluted net loss per share		$	(1.40	)		$	(0.67	)
Weighted average common stock shares outstanding used in the basic and diluted net loss per share calculation			21,830				17,017

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) 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

CONSOLIDATED STATEMENTS OF OPERATIONS

(Unaudited)

(Amounts in Thousands)

		Three months ended September 30, 2006				Three months ended October 1, 2005
						Velocity Express Standalone				Velocity + CD&L Pro Forma
Net Income (Loss)		$	(10,436	)		$	(3,497	)		$	(8,358	)
Interest Income/Expense			6,174				1,096				6,733
Income Taxes			9				0				0
Depreciation			1,272				1,109				1,303
Amortization of intangible assets			793				0				793
Stock Based Compensation			235				0				0
Other non-operating (income)/expense			(180	)			(528	)			(513	)
Transaction / Restructuring / Integration			2,929				0				0
Minority Interest in CD&L			367				0				0
Adjusted EBITDA		$	796			$	(1,820	)		$	(42	)