<PAGE>

                                                                    EXHIBIT 99.1

                    INSTRUCTIONS FOR USE OF VELOCITY EXPRESS
                        SUBSCRIPTION RIGHTS CERTIFICATES

      Consult the Velocity Express, Your Bank or Broker as to Any Questions

        The following instructions relate to a rights offering (the "Rights
Offering") by Velocity Express Corporation, a Delaware corporation (the
"Company"), to the holders of record (the "Record Holders") of its Common Stock,
par value $0.004 per share ("Common Stock"), its Series B Convertible Preferred
Stock, par value $0.004 per share ("Series B Preferred"), its Series C
Convertible Preferred Stock, par value $0.004 per share ("Series C Preferred"),
its Series D Convertible Preferred Stock, par value $0.004 per share ("Series D
Preferred"), its Series F Convertible Preferred Stock, par value $0.004 per
share ("Series F Preferred"), its Series G Convertible Preferred Stock, par
value $0.004 per share ("Series G Preferred"), its Series H Convertible
Preferred Stock, par value $0.004 per share ("Series H Preferred" and together
with the Common Stock, the Series B Preferred, the Series C Preferred, the
Series D Preferred, the Series F Preferred and the Series G Preferred, the
"Capital Stock") as described in the Company's Prospectus dated
___________________, 2003 (the "Prospectus"). Record Holders of the Capital
Stock at the close of business on September 11, 2003 (the "Record Date") are
receiving subscription rights (the "Rights") to subscribe for and purchase
shares of the Company's Series I Convertible Preferred Stock, par value $0.004
per share (the "Series I Preferred").

        Holders of Common Stock will receive 0.297952777 right for every share
of Common Stock held on the Record Date. Holders of Series B Preferred will
receive 0.486231363 rights for each share of Series B Preferred held on the
Record Date; holders of Series C Preferred will receive 0.329810541 rights for
each share of Series C Preferred held on the Record Date; holders of Series D
Preferred will receive 0.813565586 rights for each share of Series D Preferred
held on the Record Date; holders of Series F Preferred will receive 1.745371947
rights for each share of Series F Preferred held on the Record Date; holders of
Series G Preferred will receive 0.072517623 rights for each share of Series G
Preferred held on the Record Date; and holders of Series H Preferred will
receive 2.979527767 rights for each share of Series H Preferred held on the
Record Date.

        The Rights will expire, if not exercised, at 5:00 p.m., New York City
time, on _______________, 2003, unless extended in the sole discretion of the
Company (as it may be extended, the "Expiration Date"). After the Expiration
Date, unexercised Rights will be null and void. The Company will not be
obligated to honor any purported exercise of Rights received by American Stock
Transfer & Trust Company (the "Subscription Agent") after 5:00 p.m., New York
City time, on the Expiration Date, regardless of when the documents relating to
such exercise were sent, except pursuant to the Guaranteed Delivery Procedures
described below. The Company may extend the Expiration Date by giving oral or
written notice to the Subscription Agent on or before the Expiration Date,
followed by a press release no later than 9:00 a.m., New York City time, on the
next business day after the previously scheduled Expiration Date. The Rights
will be evidenced by non-transferable Rights certificates (the "Subscription
Rights Certificates").

        Each Right will entitle its holder to subscribe for one share of Series
I Preferred (the "Basic Subscription Right"). The subscription price (the
"Subscription Price") for the Series I Preferred is $2.20 per share.

        In addition, each holder of Rights who exercises his/her Basic
Subscription Right in full will be eligible to subscribe (the "Over-Subscription
Right") at the same cash price of $2.20 per share for shares of the Series I
Preferred that are not otherwise purchased pursuant to the exercise of Rights
under the Basic Subscription Right (the "Excess Shares"), subject to
availability and pro ration as described below.

<PAGE>

Each holder of Rights may only exercise his/her Over-Subscription Right if
he/she exercised his/her Basic Subscription Right in full and other holders of
subscription Rights do not exercise their Basic Subscription Right in full. If
there are not enough Excess Shares to satisfy all subscriptions made under the
Over-Subscription Right, the Company will allocate the remaining Excess Shares
pro rata, after eliminating all fractional shares, among those Rights holders
who exercised their Over-Subscription Rights. "Pro rata" means in proportion to
the amount of over-subscription price tendered by each person seeking to
oversubscribe as of the expiration date of the offering. If there is a pro rata
allocation of the remaining Excess Shares and a holder of Rights receives an
allocation of a greater number of Excess Shares than he/she subscribed for under
his/her Over-Subscription Right, then the Company will allocate to him/her only
the number of Excess Shares for which he or she subscribed. The Company will
allocate the remaining Excess Shares among all other holders exercising their
Over-Subscription Rights. See "The Rights Offering--Subscription Rights" in the
Prospectus.

        The number of Rights to which you are entitled is printed on the face of
your Subscription Rights Certificate. You should indicate your wishes with
regard to the exercise of your Rights by completing the appropriate portions of
your Subscription Rights Certificate and returning the certificate to the
Subscription Agent in the envelope provided pursuant to the procedures described
in the Prospectus.

        YOUR SUBSCRIPTION RIGHTS CERTIFICATES, OR NOTICE OF GUARANTEED DELIVERY,
AND SUBSCRIPTION PRICE PAYMENT, INCLUDING FINAL CLEARANCE OF ANY CHECKS, MUST BE
RECEIVED BY THE SUBSCRIPTION AGENT, ON OR BEFORE 5:00 P.M., NEW YORK CITY TIME,
ON THE EXPIRATION DATE. ONCE A HOLDER OF RIGHTS HAS EXERCISED THE BASIC
SUBSCRIPTION RIGHT OR THE OVER-SUBSCRIPTION RIGHT, SUCH EXERCISE MAY NOT BE
REVOKED. RIGHTS NOT EXERCISED PRIOR TO THE EXPIRATION TIME OF THE RIGHTS
OFFERING WILL EXPIRE.

        To exercise Rights, complete your Subscription Rights Certificate and
send the properly completed and executed Subscription Rights Certificate
evidencing such Rights with any signatures required to be guaranteed so
guaranteed, together with payment in full of the Subscription Price for each
share of Series I Preferred subscribed for pursuant to the Basic Subscription
Right and the Over-Subscription Right, to the Subscription Agent, on or prior to
5:00 p.m., New York City time, on the Expiration Date. Payment of the
Subscription Price will be held in a segregated account to be maintained by the
Subscription Agent. All payments must be made in U.S. dollars for the full
number of Series I Preferred being subscribed for (a) by check or bank draft
drawn upon a U.S. bank or postal, telegraphic or express money order payable to
American Stock Transfer & Trust Company, as Subscription Agent, or (b) by wire
transfer of immediately available funds, to the account maintained by the
Subscription Agent for purposes of accepting subscriptions in the Rights
Offering at ______________ ABA No. ____________, further credit to
___________________, ATTN: ___________________ (the "Subscription Account"). Any
wire transfer should clearly indicate the identity of the subscriber who is
paying the Subscription Price by the wire transfer. Payments will be deemed to
have been received by the Subscription Agent only upon (i) clearance of any
uncertified check, (ii) receipt by the Subscription Agent of any certified check
or bank draft drawn upon a U.S. bank or of any postal, telegraphic or express
money order or (iii) receipt of collected funds in the Subscription Account
designated above. If paying by uncertified personal check, please note that the
funds paid thereby may take at least five business days to clear. Accordingly,
Rights holders who wish to pay the Subscription Price by means of uncertified
personal check are urged to make payment sufficiently in advance of the
Expiration Date to ensure that such payment is received and clears by such date
and are urged to consider payment by means of certified or cashier's check,
money order or wire transfer of funds.

                                        2

<PAGE>

       The Subscription Rights Certificate and payment of the Subscription
Price, or, if applicable, Notices of Guaranteed Delivery (as defined below) must
be delivered to the Subscription Agent by one of the methods described below:

                                    By Mail:
                     American Stock Transfer & Trust Company
                                 59 Maiden Lane
                               New York, NY 10038

                          By Hand or Overnight Courier:
                     American Stock Transfer & Trust Company
                                 59 Maiden Lane
                               New York, NY 10038
                                 (718) 234-5001

                Telephone Number for Confirmation: (800) 937-5449

        Questions may be answered by, and additional copies of relevant
documents may be obtained through, contacting Wesley Fredenburg, our General
Counsel and Secretary, at:

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

        Delivery to an address other than those above does not constitute valid
delivery.

        By making arrangements with your bank or broker for the delivery of
funds on your behalf, you may also request such bank or broker to exercise the
Subscription Rights Certificate on your behalf. Alternatively, you may cause a
written guarantee substantially in the form of Exhibit A to these instructions
(the "Notice of Guaranteed Delivery"), from a member firm of a registered
national securities exchange or a member of the National Association of
Securities Dealers Corporation, or from a commercial bank or trust company
having an office or correspondent in the United States or from 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 (each, an "Eligible Institution"),
to be received by the Subscription Agent on or prior to the Expiration Date
together with payment in full of the applicable Subscription Price. Such Notice
of Guaranteed Delivery must state your name, the number of Rights represented by
the Subscription Rights Certificate or Subscription Rights Certificates held by
you, the number of Series I Preferred being subscribed for pursuant to your
Basic Subscription Right and the number of Series I Preferred, if any, being
subscribed for pursuant to the Over-Subscription Right, and that you will
guarantee the delivery to the Subscription Agent of any properly completed and
executed Subscription Rights Certificate or Subscription Rights Certificates
evidencing such Rights within three (3) business days following the date of the
Notice of Guaranteed Delivery. If this procedure is followed, the properly
completed Subscription Rights Certificate or Subscription Rights Certificates
evidencing the Rights being exercised, with any signatures required to be
guaranteed so guaranteed, must be received by the Subscription Agent within
three (3) business days following the date of the Notice of Guaranteed Delivery.
The Notice of Guaranteed Delivery may be delivered to the Subscription Agent in
the same manner as Subscription Rights Certificates at the address set forth
above, or may be transmitted to the Subscription Agent by facsimile transmission
(Facsimile No.: (718) 236-2641). Additional copies of the Notice of Guaranteed

                                        3

<PAGE>

Delivery may be obtained upon request from the Company at the address, or by
calling the telephone number, set forth above.

        Banks, brokers and other nominee holders of Rights who exercise the
Basic Subscription Right and the Over-Subscription Right on behalf of beneficial
owners of Rights will be required to certify to the Subscription Agent and the
Company, in connection with the exercise of the Over-Subscription Right, as to
the aggregate number of Rights that have been exercised and the number of Series
I Preferred that are being subscribed for pursuant to the Over-Subscription
Right, by each beneficial owner of Rights (including such nominee itself) on
whose behalf such nominee holder is acting. If more Excess Shares are subscribed
for pursuant to the Over-Subscription Right than are available for sale, the
Excess Shares will be allocated, as described above, among beneficial owners
exercising the Over-Subscription Right in proportion to the amount of
Over-Subscription price tendered by each person seeking to oversubscribe as of
the expiration date of the Rights Offering.

        If the aggregate Subscription Price paid by you is insufficient to
purchase the number of Series I Preferred subscribed for, or if no number of
Series I Preferred to be purchased is specified, then you will be deemed to have
exercised the Basic Subscription Right to purchase Series I Preferred to the
full extent of the payment tendered.

        If the aggregate Subscription Price paid by you exceeds the amount
necessary to purchase the number of Series I Preferred for which you have
indicated an intention to subscribe (such excess being the "Subscription
Excess"), then you will be deemed to have exercised the Over-Subscription Right
to the full extent of the excess payment tendered, to purchase, to the extent
available, that number of Series I Preferred equal to the quotient obtained by
dividing the Subscription Excess by the Subscription Price. Any remaining amount
shall be returned to you by mail without interest or deduction as soon as
practicable after the Expiration Date and after all pro rations and adjustments
contemplated by the terms of the Rights Offering have been effected.

        The following deliveries and payments will be made to the address shown
on the face of your Subscription Rights Certificate unless you provide
instructions to the contrary in your Subscription Rights Certificate.

                (a)     Basic Subscription Right. As soon as practicable after
        the Expiration Date and the valid exercise of Rights, the Subscription
        Agent will mail to each exercising Rights holder certificates
        representing shares of Series I Preferred purchased pursuant to the
        Basic Subscription Right. See "The Rights Offering--Subscription
        Rights--Basic Subscription Right" in the Prospectus.

                (b)     Over-Subscription Right. As soon as practicable after
        the Expiration Date and after all pro rations and adjustments
        contemplated by the terms of the Rights Offering have been effected, the
        Subscription Agent will mail to each Rights holder who validly exercises
        the Over-Subscription Right certificates representing the number of
        shares of Series I Preferred, if any, allocated to such Rights holder
        pursuant to the Over-Subscription Right. See "The Rights
        Offering--Subscription Rights--Over-Subscription Right" in the
        Prospectus.

                (c)     Excess Cash Payments. As soon as practicable after the
        Expiration Date and after all pro rations and adjustments contemplated
        by the terms of the Rights Offering have been effected, the Subscription
        Agent will mail to each Rights holder who exercises the
        Over-Subscription Right any excess amount, without interest or
        deduction, received in payment of the Subscription Price for Excess
        Shares that are subscribed for by such Rights holder but not allocated
        to such Rights holder pursuant to the Over-Subscription Right.

                                        4

<PAGE>

        The Company will pay all fees and expenses of the Subscription Agent and
has also agreed to indemnify the Subscription Agent from certain liabilities
that they may incur in connection with the Rights Offering.

        The signature on the Subscription Rights Certificate must correspond
with the name of the registered holder exactly as it appears on the face of the
Subscription Rights Certificate without any alteration or change whatsoever.
Persons who sign the Subscription Rights Certificate in a representative or
other fiduciary capacity must indicate their capacity when signing and, unless
waived by the Subscription Agent in its sole and absolute discretion, must
present to the Subscription Agent satisfactory evidence of their authority to so
act.

        If the Subscription Rights Certificate is executed by a person other
than the holder named on the face of the Subscription Rights Certificate, proper
evidence of authority of the person executing the Subscription Rights
Certificate must accompany the same unless, for good cause, the Subscription
Agent dispenses with proof of authority.

        Your signature must be guaranteed by an Eligible Institution if you
specify special payment or delivery instructions.

        The method of delivery of Subscription Rights Certificates and payment
of the Subscription Price to the Subscription Agent will be at the election and
risk of the Rights holder, but, if sent by mail, it is recommended that such
certificates and payments be sent by registered mail, properly insured, with
return receipt requested, and that a sufficient number of days be allowed to
ensure delivery to the Subscription Agent and the clearance of payment prior to
5:00 p.m., New York City time, on the Expiration Date. Because uncertified
personal checks may take at least five business days to clear, you are strongly
urged to pay, or arrange for payment, by means of certified or cashier's check,
money order or wire transfer of funds.

                                        5

<PAGE>

                                                                       EXHIBIT A

                          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

                                       A-1

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

                                       A-1

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

