Exhibit 99.1

[LOGO OF VELOCITY EXPRESS]

FOR IMMEDIATE RELEASE

VELOCITY EXPRESS ANNOUNCES RECEIPT OF NEW NASDAQ LETTER

MINNEAPOLIS, MN, December 28, 2004—Velocity Express Corporation (NASDAQ:VEXEC) (the “Company”) today announced the receipt on December 22, 2004 of a letter from the Nasdaq Listing Qualifications Staff, which notified the Company that its common stock will continue to be listed on the Nasdaq SmallCap Market pursuant to exceptions from the filing, proxy solicitation, annual shareholders’ meeting and bid price requirements in Nasdaq Marketplace Rules 4310(c)(14), 4350(e), 4350(g) and 4310(c)(4), respectively.

The Company failed to timely file its Form 10-K for the fiscal year ended July 3, 2004 (the “10-K”), and also failed to timely file its Form 10-Q for the first quarter of fiscal year 2005 (the “10-Q”). The Company also failed to hold its annual shareholders’ meeting for fiscal year 2003. Finally, the Company has a commitment to Nasdaq to seek, at its next shareholders’ meeting to be held no later than January 20, 2005, shareholder approval of a reverse stock split to address the Company’s deficiency in meeting its required minimum bid price. The Company discussed these matters at a hearing before the Nasdaq Listing Qualifications Panel (the “Panel”) on November 18, 2004.

The Panel has granted the Company temporary exceptions to its listing requirements subject to the Company meeting certain conditions. On or before January 14, 2005, the Company must file the delinquent 10-K and 10-Q. Furthermore, on or before February 15, 2005, the Company must (a) file its Form 10-Q for the quarter ending on or about December 31, 2004; (b) solicit proxies and hold a shareholders’ meetings for fiscal years 2003 and 2004, and to approve the reverse stock split; and (c) evidence a closing bid price of at least $1.00 per share, and, immediately thereafter, a closing bid price of at least $1.00 per share for a minimum of ten consecutive trading days. The Panel has reserved the ability to require that the Company maintain the minimum bid price for a period in excess of 10 days before determining that the Company has satisfied this condition.

All companies on the Nasdaq SmallCap Market operating under exceptions are identified by the appendage of a “C” to their trading symbol. Accordingly, as of open of business on December 27, 2004, the trading symbol for the Company is “VEXEC.” The “E” and “C” will be removed from the Company’s trading symbol upon the Panel’s determination that the Company has complied with the Nasdaq filing requirements and all terms of the exceptions described above.

On December 23, 2005 the Company filed its Form 10-K for the fiscal year ended July 3, 2004. The Company intends to file an amended Form 10-K relative only to the beneficial ownership tables in Item 12 of Part III.

In the event the Panel ultimately finds that the Company has met these conditions, the Company shall continue to be listed on the Nasdaq SmallCap Market. The Company is working diligently with its auditors to meet these conditions, but there can be no assurance it will do so. The Company may subsequently need to request additional time to solicit proxies and hold its shareholders’ meeting for good cause, such as, for example, SEC review.

About Velocity Express

Velocity Express has one of the largest time critical nationwide networks and provides 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 which provides customers the ability to view the status of any package via a flexible web reporting system.

This press release includes certain “forward-looking statements” for purposes of the “safe harbor” provisions of the Private Securities Litigation Reform Act of 1995 that involve risks and uncertainties that could cause actual results to differ materially. Such statements are based upon, among other things, assumptions made by, and information currently available to, management, including management’s own knowledge and assessment of Velocity Express’s industry and competition. The Company disclaims any obligations to update any forward-looking statement as a result of developments occurring after the date of this press release.

###

Contact:

Steven S. Anreder, 212/532-3232

steven.anreder@anreder.com

or

Velocity Express, Minneapolis

Wes Fredenburg, 612/492-2405

wfredenburg@velocityexp.com

2