<PAGE>

                                                                    EXHIBIT 99.2

                          NOTICE OF GUARANTEED DELIVERY
                                       FOR
                     SUBSCRIPTION RIGHTS CERTIFICATES ISSUED
                         BY VELOCITY EXPRESS CORPORATION

        This form, or one substantially equivalent hereto, must be used to
exercise Rights pursuant to the Rights Offering described in the Prospectus
dated ___________________, 2003 (the "Prospectus") of Velocity Express
Corporation, a Delaware corporation (the "Company"), if a holder of Rights
cannot deliver the certificate(s) evidencing the Rights (the "Subscription
Rights Certificate(s)"), to the Subscription Agent listed below (the
"Subscription Agent") at or prior to 5:00 p.m., New York City time, on
___________________, 2003, unless such time is extended, or the Rights Offering
is terminated, each as may be determined by the Company as described in the
Prospectus (as it may be extended or terminated, the "Expiration Date"). Such
form must be delivered by hand or sent by telegram, facsimile transmission,
first class mail or overnight courier to the Subscription Agent, and must be
received by the Subscription Agent on or prior to the Expiration Date. See "The
Rights Offering--Method of Subscription--Exercise of Rights" in the Prospectus.
Payment of the Subscription Price of $2.20 per share for each share of the
Company's Series I Convertible Preferred Stock, par value $0.004 ("Series I
Preferred"), subscribed for upon exercise of such Rights must be received by the
Subscription Agent in the manner specified in "The Rights Offering--Method of
Payment" in the Prospectus at or prior to 5:00 p.m., New York City time on the
Expiration Date even if the Subscription Rights Certificate(s) evidencing such
Rights is (are) being delivered pursuant to the Guaranteed Delivery Procedures
thereof. See "The Rights Offering--Method of Subscription--Exercise of Rights"
in the Prospectus.

                           The Subscription Agent is:

                     AMERICAN STOCK TRANSFER & TRUST COMPANY

       If by Mail or Telegram:               If by Hand or Overnight Courier:
American Stock Transfer & Trust Company  American Stock Transfer & Trust Company
           59 Maiden Lane                            59 Maiden Lane
         New York, NY 10038                        New York, NY 10038
        Confirm by Telephone:                    Facsimile Transmission:
          (800) 937-5449                            (718) 234-5001

        DELIVERY OR TRANSMISSION OF THIS INSTRUMENT OTHER THAN AS SET FORTH
ABOVE DOES NOT CONSTITUTE A VALID DELIVERY.

        Questions may be answered by, and additional copies of relevant
documents may be obtained through contacting the Company's General Counsel and
Secretary, Wesley Fredenburg:

                          Velocity Express Corporation
                          7803 Glenroy Road, Suite 200
                          Minneapolis, Minnesota 55439
                                 (612) 492-2405

<PAGE>

Ladies and Gentlemen:

        The undersigned hereby represents that the undersigned is the holder of
Subscription Rights Certificate(s) representing ___________________ Rights and
that such Subscription Rights Certificate(s) cannot be delivered to the
Subscription Agent at or before 5:00 p.m., New York City time, on the Expiration
Date. Upon the terms and subject to the conditions set forth in the Prospectus,
receipt of which is hereby acknowledged, the undersigned hereby elects to
exercise (i) the Basic Subscription Right to subscribe for ________ share(s) of
Series I Preferred with respect to each of the Rights represented by such
Subscription Rights Certificate(s) and (ii) the Over-Subscription Right relating
to such Rights, to the extent that shares of Series I Preferred that are not
otherwise purchased pursuant to the exercise of the Basic Subscription Rights
(the "Excess Shares") are available therefor, for an aggregate of up to Excess
Shares, subject to availability and pro ration.

        The undersigned understands that payment of the Subscription Price of
$2.20 per share for each share of Series I Preferred subscribed for pursuant to
the Basic Subscription Right and the Over-Subscription Right must be received by
the Subscription Agent at or before 5:00 p.m., New York City time, on the
Expiration Date and represents that such payment, in the aggregate amount of
$___________, either (check appropriate box):

        [ ]     is being delivered to the Subscription Agent herewith;

        or

        [ ]     has been delivered separately to the Subscription Agent in the
                manner set forth below (check appropriate box and complete
                information relating thereto):

        [ ]     Wire transfer of funds

                Name of transferor institution: _______________________________

                Date of transfer: _______________________________

                Confirmation number (if available):_____________________________

        [ ]     Uncertified check (Payment by uncertified check will not be
                deemed to have been received by the Subscription Agent until
                such check has cleared. Holders paying by such means are urged
                to make payment sufficiently in advance of the Expiration Date
                to ensure that such payment clears by such date.)

        [ ]     Certified check

        [ ]     Bank draft (cashier's check)

<PAGE>

        [ ]     Money order

                Name of maker: _______________________________

                Date of check, draft or money order:____________________________

                Check, draft or money order number:-____________________________

                Bank or other institution on which check is drawn or issuer of
                money order: _______________________________

Signature(s)


---------------------------

Name(s)


---------------------------
(PLEASE TYPE OR PRINT)

ADDRESS

---------------------------

---------------------------

---------------------------

---------------------------
Area Code and Tel. No.(s)


Subscription Rights Certificates No(s). (if available)


---------------------------

<PAGE>

                              GUARANTEE OF DELIVERY
    (NOT TO BE USED FOR SUBSCRIPTION RIGHTS CERTIFICATE SIGNATURE GUARANTEE)

        The undersigned, a member firm of a registered national securities
exchange or of the National Association of Securities Dealers Corporation, or a
commercial bank or trust company having an office or correspondent in the United
States, or a bank, stockbroker, savings and loan association or credit union
with membership in an approved signature guarantee medallion program, pursuant
to Rule 17Ad-15 of the Securities Exchange Act of 1934, as amended, guarantees
that the undersigned will deliver to the Subscription Agent the certificates
representing the Rights being exercised hereby, with any required signature
guarantee and any other required documents, all within three (3) business days
after the date hereof.


Dated:

---------------------


------------------------------------            --------------------------------
            (Address)                                    (Name of Firm)


------------------------------------            --------------------------------
  (Area Code and Telephone Number)                   (Authorized Signature)

        The institution that completes this form must communicate the guarantee
to the Subscription Agent and must deliver the Subscription Rights
Certificate(s) to the Subscription Agent within the time period shown in the
Prospectus of Velocity Express Corporation, dated ___________________, 2003.
Failure to do so could result in a financial loss to such institution.

