<PAGE>


                                  UNITED STATES
                       SECURITIES AND EXCHANGE COMMISSION
                             Washington, D.C. 20549

                         Commission File Number: 0-28452

                                   FORM 12b-25
                           NOTIFICATION OF LATE FILING

    [ ] Form 10-K [ ] Form 20-F [ ] Form 11-K [.X.] Form 10-Q [ ] Form N-SAR

                      For Period Ended: September 27, 2003

               [ ] Transition Report on Form 10-K
               [ ] Transition Report on Form 20-F
               [ ] Transition Report on Form 11-K
               [ ] Transition Report on Form 10-Q
               [ ] Transition Report on Form N-SAR
               For the Transition Period Ended: ______________________

     Nothing in this form shall be construed to imply that the Commission has
verified any information contained herein.

     If the notification relates to a portion of the filing checked above,
identify the Item(s) to which the notification relates: N/A


PART I-REGISTRANT INFORMATION

     Full Name of Registrant:                    Velocity Express Corporation
     Former Name if Applicable:
     Address of Principal Executive Office:      7803 Glenroy Road, Suite 200
     City, State and Zip Code:                   Minneapolis, Minnesota  55439

PART II-RULES 12b-25(b) AND (c)

     If the subject report could not be filed without unreasonable effort or
expense and the registrant seeks relief pursuant to Rule 12b-25(b), the
following should be completed. (Check box if appropriate) [X]

     (a)  The reasons described in reasonable detail in Part III of this form
          could not be eliminated without unreasonable effort or expense;
     (b)  The subject annual report, semi-annual report, transition report on
          Form 10-K, Form 20-F, Form 11-K, Form N-SAR, or portion thereof, will
          be filed on or before the fifteenth calendar day following the
          prescribed due date; or the subject quarterly report or transition
          report on Form 10-Q, or portion thereof will be filed on or before the
          fifth calendar day following the prescribed due date; and
     (c)  The accountant's statement or other exhibit required by Rule 12b-25(c)
          has been attached if applicable.

<PAGE>
PART III-NARRATIVE

     State below in reasonable detail the reasons why Forms 10-K, 20-F, 11-K,
10-Q, N-SAR, or the transition report or portion thereof, could not be filed
within the prescribed time period.

     The Registrant is in the process of refinancing its revolving credit and
senior subordinated debt facilities, which will not be concluded in time to
permit timely filing and which, when concluded, could affect the required
disclosures related thereto.

     For the reasons set forth above, the Registrant cannot timely file its
Quarterly Report on Form 10-Q without unreasonable effort or expense. Management
believes Form 10-Q will be completed on or before November 17, 2003.

PART IV-OTHER INFORMATION

(1)  Name and telephone number of person to contact in regard to this
     notification

         Wesley C. Fredenburg             (612)                492-2405
     ----------------------------    --------------     -----------------------
               (Name)                  (Area Code)         (Telephone Number)

(2)  Have all other periodic reports required under Section 13 or 15(d) of the
     Securities Exchange Act of 1934 or Section 30 of the Investment Company Act
     of 1940 during the preceding 12 months or for such shorter period that the
     registrant was required to file such report(s) been filed? If answer is no,
     identify report(s).

     [X] Yes           [  ] No

(3)  Is it anticipated that any significant change in results of operations from
     the corresponding period for the last fiscal year will be reflected by the
     earnings statements to be included in the subject report or portion
     thereof?

     [  ] Yes          [X] No

     If so, attach an explanation of the anticipated change, both narratively
and quantitatively, and, if appropriate, state the reasons why a reasonable
estimate of the results cannot be made.

                          Velocity Express Corporation
                -------------------------------------------------
                  (Name of Registrant as Specified in Charter)

     has caused this notification to be signed on its behalf by the undersigned
hereunto duly authorized.


     Date  November 12, 2003             By   /s/ Wesley C. Fredenburg
          --------------------               -----------------------------------
                                             Wesley C. Fredenburg
                                             Secretary and General Counsel

     INSTRUCTION: The form may be signed by an executive officer of the
registrant or by any other duly authorized representative. The name and title of
the person signing the form shall be typed or printed beneath the signature. If
the statement is signed on behalf of the registrant by an authorized
representative (other than an executive officer), evidence of the
representative's authority to sign on behalf of the registrant shall be filed
with the form.

