Exhibit 99.1

VELOCITY EXPRESS ANNOUNCES RECEIPT OF NASDAQ LISTING DECISION

WESTPORT, Conn., August 4, 2009 – (BUSINESS WIRE)—Velocity Express Corporation (NASDAQ:VEXP), the nation’s largest provider of time definite regional delivery solutions, announced today that it has received notification that NASDAQ will not grant the Company a further extension within which to regain compliance with the applicable NASDAQ listing requirements. Therefore, trading in the Company’s stock will be transferred from The NASDAQ Capital Market to the over-the-counter market, effective at the market opening on August 5, 2009.

The Company had requested an extension because the closing of the Recapitalization Agreement approved by the Independent Directors on July 31 would result in the Company regaining compliance with the $2.5 million Stockholders’ Equity requirement for continued listing on The NASDAQ Capital Market; however, it cannot be completed until after Shareholder Approval, which will occur in mid-September.

The Company’s securities are immediately eligible for quotation in the Pink Sheets, an electronic quotation service for securities traded over-the-counter, effective with the open of business on Wednesday, August 5, 2009. The Company’s trading symbol will remain VEXP. However, it is the Company’s understanding that, for certain quote publication websites, investors may be required to key VEXP.PK to obtain quotes. The Company’s common stock may, in the future, also be quoted on the Over-the-Counter Bulletin Board, an electronic quotation service maintained by the Financial Industry Regulatory Authority (“FINRA”), provided that a market maker in the Company’s common stock files the appropriate application with, and such application is cleared by, FINRA. In such an event, the Company’s trading symbol would also remain as VEXP. However, it is the Company’s understanding that, for certain quote publication websites, investors may be required to key VEXP.OB to obtain quotes.

About Velocity Express

Velocity Express has one of the largest nationwide networks of regional, time definite, ground delivery service areas, 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.

About Pink Sheets LLC

Pink Sheets provides broker-dealers, issuers and investors with electronic and print products and information services designed to improve the transparency of the Over-the-Counter (OTC) markets. The products are designed to increase the efficiency of OTC markets, leading to greater liquidity and investor interest in OTC securities. Pink Sheets centralized information network is a source of competitive market maker quotations, historical prices and corporate information about OTC issues and issuers. Pink Sheets is neither an SEC-Registered Stock Exchange nor a FINRA Broker/Dealer. Investors must contact a FINRA Broker/Dealer to trade in a security quoted on the Pink Sheets. Pink Sheets LLC is a privately owned company headquartered in New York City. More information is available at http://www.pinksheets.com.]

About the OTCBB:

The OTCBB is a regulated quotation service that displays real-time quotes, last-sale prices, and volume information in over the counter equity securities. An over the counter equity security generally is any equity that is not listed or traded on a national securities exchange. OTCBB securities include national, regional, and foreign equity issues, warrants, units, ADRs, and Direct Participation Programs. More information is available at http://www.otcbb.com.

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. 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 as identified in the section entitled “Risk Factors” in the Company’s Annual Report on Form 10-K for the year ended June 28, 2008 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, CFO

203-349-4199

tstone@velocityexp.com

or

Institutional Marketing Services (IMS)

John G. Nesbett/Jennifer Belodeau

203-972-9200

jnesbett@institutionalms.com