<PAGE>

                                                                       EXHIBIT 8

          IMPORTANT: PLEASE READ CAREFULLY BEFORE SIGNING: SIGNIFICANT
                     REPRESENTATIONS ARE CALLED FOR HEREIN.

                          VELOCITY EXPRESS CORPORATION

                            STOCK PURCHASE AGREEMENT

Velocity Express Corporation
7803 Glenroy Road, Suite 200
Bloomington, Minnesota 55439

Ladies and Gentlemen:

      THIS STOCK PURCHASE AGREEMENT (the "Purchase Agreement"), made effective
this 20th day of October 2003, by and between Velocity Express Corporation, a
Delaware corporation (the "Company"), and TH Lee Putnam Ventures, L.P., TH Lee
Putnam Parallel Ventures, L.P., THLi Coinvestment Partners, LLC and Blue Star I,
LLC (collectively referred to herein as "undersigned" or "THLPV"), each with a
principal place of business in New York.

1.    (a)   The Company agrees to sell to the undersigned, and the
            undersigned agrees to purchase from the Company, 2,000,000 shares of
            the Company's Series I Convertible Preferred Stock, par value $0.004
            per share (the "Shares" or "Series I Preferred") for the
            subscription price per Share listed in paragraph 1(b) below. The
            rights and preferences of the Shares are set forth in the
            Certificate of Designation of Preferences and Rights of Series I
            Convertible Preferred Stock as set forth in Appendix A attached
            hereto. The undersigned acknowledges that this subscription is
            contingent upon acceptance in whole or in part by the Company and
            upon shareholder approval of (i) the issuance of the Series I
            Preferred Stock and (ii) the amendment of the Company's Certificate
            of Incorporation to increase the number of shares authorized for
            issuance to 400,000,000 shares, of which 325,000,000 shares are
            Common Stock and 75,000,000 shares are Preferred Stock, at a meeting
            of the Company's shareholders or by written consent. Concurrent with
            the delivery of this Agreement, the undersigned has delivered cash
            or a check or wire transfer to the Company in the amount of $
            3,000,000 for payment of the full purchase price of the Shares.

      (b)   Subject to the Board of Directors of the Company varying the
            purchase price per share of the Series I Preferred if they deem such
            action necessary or appropriate to obtain sufficient funding for the
            Company, the Series I Preferred shall be sold at the following price
            per Share (the "Purchase Price"):

      -     if this Purchase Agreement is executed and the payment of the
            Purchase Price is tendered to the Company on or before October 24,
            2003, the Purchase Price shall be $1.50 per Share;

      -     if this Purchase Agreement is executed and the payment of the
            Purchase Price is tendered to the Company after October 24, 2003,
            but on or before October 31, 2003, the Purchase Price shall be $1.80
            per Share;
<PAGE>
      -     if this Purchase Agreement is executed and the payment of the
            Purchase Price is tendered to the Company after October 31, 2003,
            but on or before November 14, 2003, the Purchase Price shall be
            $2.20 per Share; and

      -     if this Purchase Agreement is executed and the payment of the
            Purchase Price is tendered to the Company after November 14, 2003,
            but on or before November 28, 2003, the Purchase Price shall be
            $3.30 per Share.

      (c)   The Company and the undersigned agrees that if the shareholder
            approval specified in paragraph 1(a) above is not achieved, the
            Company will return to the undersigned, without interest or
            deduction, any Purchase Price tendered by the undersigned for the
            purchase of the Series I Preferred.

2.          The undersigned acknowledges and represents as follows:

      (a)   That the undersigned has had an opportunity to carefully review the
            Company, has had the opportunity to conduct due diligence on the
            Company, has had the opportunity to review its public filings with
            the Securities and Exchange Commission and has reviewed the Risk
            Factors, attached hereto as Appendix B, relating to the Company (the
            "Company Materials"), and all documents delivered therewith or
            reasonably requested by the undersigned and is aware of the fact
            that the Company may use a portion of the funds generated from the
            sale of the Series I Preferred to replace certain letters of credit
            totally $7.1 million currently maintained by the Company and
            guaranteed by TH Lee Putnam Ventures;

      (b)   That the undersigned is able to bear the economic risk of the
            investment in the Shares;

      (c)   That the undersigned has knowledge and experience in financial and
            business matters, that the undersigned is capable of evaluating the
            merits and risks of the prospective investment in the Shares and
            that the undersigned is able to bear such risks.

      (d)   That the undersigned understands an investment in the Shares is
            highly speculative but believes that the investment is suitable for
            the undersigned based upon the investment objectives and financial
            needs of the undersigned, and has adequate means for providing for
            his, her or its current financial needs and personal contingencies
            and has no need for liquidity of investment with respect to the
            Shares;

      (e)   That the undersigned has been given access to full and complete
            information regarding the Company (including the opportunity to meet
            with Company officers and review such documents as the undersigned
            may have requested in writing) and has utilized such access to the
            satisfaction of the undersigned for the purpose of obtaining
            information in addition to, or verifying information included in,
            the Company Materials;

      (f)   That the undersigned recognizes that the Shares, are an investment,
            involve a high degree of risk, including, but not limited to, the
            risks described in the Company Materials;

      (g)   That the undersigned realizes that (i) the purchase of Shares is a
            long-term investment; (ii) the purchasers of the Shares must bear
            the economic risk of investment for an indefinite period of time
            because the Shares have not been registered under the Securities Act
            of 1933, as amended (the "Act") and, therefore, cannot be sold
            unless they are subsequently registered under the Act, or an
            exemption from such registration is


                                       2
<PAGE>
            available; and (iii) the transferability of the Shares is
            restricted, and (A) requires the written consent of the Company, (B)
            requires conformity with the restrictions contained in paragraph 3
            below, and (C) will be further restricted by a legend placed on the
            certificate(s) representing the Shares stating that the Shares have
            not been registered under the Act and referring to the restrictions
            on transferability of the Shares, and by stop transfer orders or
            notations on the Company's records referring to the restrictions on
            transferability;

      (h)   That the undersigned is a bona fide resident of, and is domiciled
            in, the state or country listed in the Recital to this Agreement and
            that the Shares are being purchased solely for the beneficial
            interest of the undersigned and not as nominee, for, or on behalf
            of, or for the beneficial interest of, or with the intention to
            transfer to, any other person, trust or organization, except as
            specifically set forth in paragraph 4 of this Purchase Agreement;

      (i)   That pending shareholder authorization specified in paragraph 1(a)
            above, the Purchase Price received by the Company pursuant to this
            Purchase Agreement and other stock purchase agreements for the
            subscription of the Series I Preferred shall be used for the general
            corporate purposes of the Company and will not be held in a
            segregated account;

      (j)   That the Company did not solicit the undersigned in connection with
            its rights offering described in the Company's Registration
            Statement filed on October 1, 2003, (File Number 333-109362) and
            which was later withdrawn;

      (k)   That there is no minimum amount for the Company's offering of the
            Series I Preferred and that there can be no assurance that the
            offering of the Series I Preferred will result in a total proceeds
            to the Company of any set amount; and

      (l)   That the undersigned constitutes an accredited investor as defined
            in Rule 501(a) under the Securities Act of 1933.

3.          The undersigned has been advised that the Shares are not being
            registered under the Act or any other securities laws pursuant to
            exemptions from the Act and such laws, and that the Company's
            reliance upon such exemptions is predicated in part on the
            undersigned's representations to the Company as contained herein.
            The undersigned represents and warrants that the Shares are being
            purchased for his, her or its own account and for investment and
            without the intention of reselling or redistributing the same, that
            he, she or it has made no agreement with others regarding any of
            such Shares and that his, her or its financial condition is such
            that it is not likely that it will be necessary to dispose of any of
            such Shares in the foreseeable future. The undersigned is aware
            that, in the view of the Securities and Exchange Commission, a
            purchase of Shares with an intent to resell by reason of any
            foreseeable specific contingency or anticipated change in market
            value, or any change in the condition of the Company or its
            business, or in connection with a contemplated liquidation or
            settlement of any loan obtained for the acquisition of the Shares
            and for which the Shares were pledged as security, would represent
            an intent inconsistent with the representations set forth above. The
            undersigned further represents and agrees that if, contrary to his,
            her or its foregoing intentions, he, she or it should later desire
            to dispose of or transfer any of such Shares in any manner, he, she
            or it shall not do so without first obtaining (a) the opinion of
            counsel designated by the Company that such proposed disposition or
            transfer lawfully may be made without the registration of such
            Shares for such purpose pursuant to the Act, as then in effect, and
            any other applicable


                                       3
<PAGE>
            securities laws, or (b) such registrations (it being expressly
            understood that the Company shall not have any obligation to
            register the Shares for such purpose).

                  The undersigned agrees that the Company may place a
            restrictive legend on the certificate(s) representing the Shares,
            containing substantially the following language:

      THE SECURITIES REPRESENTED BY THIS CERTIFICATE WERE ISSUED WITHOUT
      REGISTRATION UNDER THE SECURITIES ACT OF 1933, AS AMENDED (THE "ACT"), AND
      WITHOUT REGISTRATION UNDER ANY OTHER SECURITIES LAWS, IN RELIANCE UPON
      EXEMPTIONS CONTAINED IN THE ACT AND SUCH LAWS. NO TRANSFER OF THESE
      SECURITIES OR ANY INTEREST THEREIN MAY BE MADE IN THE ABSENCE OF EITHER AN
      EFFECTIVE REGISTRATION STATEMENT UNDER THE ACT AND UNDER THE APPLICABLE
      STATE SECURITIES LAWS, OR AN OPINION OF COUNSEL ACCEPTABLE TO THE COMPANY
      THAT SUCH TRANSACTION IS EXEMPT FROM REGISTRATION UNDER THE ACT AND UNDER
      APPLICABLE STATE SECURITIES LAWS. FURTHER, THESE SECURITIES ARE SUBJECT TO
      LIMITATIONS ON CONVERTIBILITY AS SET FORTH IN THE STOCK PURCHASE AGREEMENT
      APPLICABLE TO THE ISSUANCE OF THESE SECURITIES AND THE CERTIFICATE OF
      DESIGNATION OF THOSE SECURITIES.

                  The undersigned agrees and consents that the Company may place
            a stop transfer order on the certificate(s) representing the Shares
            to assure the undersigned's compliance with this Agreement and the
            matters referenced above.

                  The undersigned agrees to save and hold harmless, defend and
            indemnify the Company and its directors, officers and agents from
            any claims, liabilities, damages, losses, expenses or penalties
            arising out of any misrepresentation of information furnished by the
            undersigned to the Company in this Agreement.

            The undersigned understands that the Company at a future date may
            file a registration or offering statement (the "Registration
            Statement") with the Securities and Exchange Commission to
            facilitate a public offering of its securities. The undersigned
            agrees, for the benefit of the Company, that should an underwritten
            public offering be made and should the managing underwriter of such
            offering require, the undersigned will not, without the prior
            written consent of the Company and such underwriter, during the Lock
            Up Period as defined herein: (a) sell, transfer or otherwise dispose
            of, or agree to sell, transfer or otherwise dispose of any of the
            Shares beneficially held by the undersigned during the Lock Up
            Period; (b) sell, transfer or otherwise dispose of, or agree to
            sell, transfer or otherwise dispose of any options, rights or
            warrants to purchase any of the Shares beneficially held by the
            undersigned during the Lock Up Period; or (c) sell or grant, or
            agree to sell or grant, options, rights or warrants with respect to
            any of the Shares. The foregoing does not prohibit gifts to donees
            or transfers by will or the laws of descent to heirs or
            beneficiaries provided that such donees, heirs and beneficiaries
            shall be bound by the restrictions set forth herein. The term "Lock
            Up Period" shall mean the lesser of (x) 240 days or (y) the period
            during which Company officers and directors are restricted by the
            managing underwriter from effecting any sales or transfers of the
            Company's securities. The Lock Up Period shall commence on the
            effective date of the Registration Statement.


                                       4
<PAGE>
            The undersigned has read and executed the Registration Rights
            Agreement in the form appended hereto as Appendix C. The undersigned
            agrees that, notwithstanding any registration rights granted under
            the Registration Rights Agreement, the undersigned will not be
            entitled to any registration rights, whether by demand, piggyback or
            otherwise, until the shareholder approval of (i) the issuance of the
            Series I Preferred Stock and (ii) the amendment of the Company's
            Certificate of Incorporation to increase the number of shares
            authorized for issuance to 400,000,000 shares, of which 325,000,000
            shares are Common Stock and 75,000,000 shares are Preferred Stock,
            at a meeting of the Company's shareholders or by written consent has
            been obtained.

4.          NASD Affiliation. The undersigned is affiliated or associated,
            directly or indirectly, with a National Association of Securities
            Dealers, Inc. ("NASD") member firm or person.

                  Yes                           No
                     ---------                    ---------

                  If yes, list the affiliated member firm or person:
                                                                    ------------

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

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

            Your relationship to such member firm or person:
                                                            -----

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

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

5.          Entities. If the undersigned is not an individual but an entity, the
            individual signing on behalf of such entity and the entity jointly
            and severally agree and certify that:

      A.    The undersigned was not organized for the specific purpose of
            acquiring securities of the Company; and

      B.    This Agreement has been duly authorized by all necessary action on
            the part of the undersigned, has been duly executed by an authorized
            officer or representative of the undersigned, and is a legal, valid
            and binding obligation of the undersigned enforceable in accordance
            with its terms.

6.          The undersigned agrees that he/she or it shall not disclose either
            the existence, the contents or any of the terms and conditions of
            this Purchase Agreement to any other person.

7.          Miscellaneous.

      A.    Manner in which title is to be held: (check one)

                        Individual Ownership
                  -----

                        Joint Tenants with Right of Survivorship*
                  -----


                                       5
<PAGE>
                        Partnership*
                  -----

                        Tenants in Common*
                  -----

                        Corporation
                  -----

                        Trust
                  -----

                        Other
                  -----       ------------------------------------
                                                                   describe)
                  ------------------------------------------------

      B.    The undersigned agrees that the undersigned understands the meaning
            and legal consequences of the agreements, representations and
            warranties contained herein, agrees that such agreements,
            representations and warranties shall survive and remain in full
            force and effect after the execution hereof and payment for the
            Shares, and further agrees to indemnify and hold harmless the
            Company, each current and future officer, director, employee, agent
            and shareholder from and against any and all loss, damage or
            liability due to, or arising out of, a breach of any agreement,
            representation or warranty of the undersigned contained herein.

      C.    This Agreement shall be construed and interpreted in accordance with
            Minnesota law without regard to conflict of law provisions.

      D.    The undersigned agrees to furnish to the Company, upon request, such
            additional information as may be deemed necessary to determine the
            undersigned's suitability as an investor.


-------------
* Multiple signatures required


                                       6
<PAGE>
                                 SIGNATURE PAGE

Accepted as of October 20, 2003


------------------------------------
Velocity Express Corporation
By:


TH Lee Putnam Ventures, L.P.
(f/k/a TH Lee.Putnam Internet Partners, L.P.)

By: TH Lee Putnam Fund Advisors, L.P.,
its General Partner
By: TH Lee Putnam Fund Advisors, LLC.,
its General Partner


------------------------------------
Name: Doug Hsieh
Title: Principal

TH Lee Putnam Parallel Ventures, L.P.
(f/k/a TH Lee.Putnam Internet Parallel
Partners, L.P.)

By: TH Lee Putnam Fund Advisors, L.P.,
its General Partner
By: TH Lee Putnam Fund Advisors, LLC.,
its General Partner


------------------------------------
Name: Doug Hsieh
Title: Principal

THLi Coinvestment Partners, LLC


------------------------------------
Name: Doug Hsieh
Title: Principal

Blue Star I, LLC

By:
   ---------------------------------
Name: Thomas H, Lee
Title: Sole Member


                                       7
<PAGE>
                            CERTIFICATE OF SIGNATORY

(To be completed if Shares are being subscribed by an entity.)

      I,                         , am the               ,
(the "Entity").

      I certify that I am empowered and duly authorized by the Entity to execute
and carry out the terms of the Stock Purchase Agreement, dated           , 2003,
by and between Velocity Express Corporation and the Entity to purchase and hold
the Shares, and certify further that the Stock Purchase Agreement has been duly
and validly executed on behalf of the Entity and constitutes a legal and binding
obligation of the Entity.

      IN WITNESS WHEREOF, I have set my hand this       day of      , 2003.



                                       ----------------------------------------
                                       (Signature)


                                       ----------------------------------------
                                       (Title)


                                       ----------------------------------------
                                       (Please Print Name)


                                       8
<PAGE>
                            ACCEPTANCE BY THE COMPANY

      Velocity Express Corporation hereby accepts the foregoing subscription to
the extent of 2,000,000 Shares and shall issue such Shares upon shareholder
approval of (i) the issuance of the Series I Preferred Stock and (ii) the
amendment of the Company's Certificate of Incorporation to increase the number
of shares authorized for issuance to 400,000,000 shares, of which 325,000,000
shares are Common Stock and 75,000,000 shares are Preferred Stock, at a meeting
of the Company's shareholders to be held no later than [January 31, 2004] or by
written consent executed no later than [January 31, 2004].

Velocity Express Corporation

By
  ----------------------------------------
            Wesley C. Fredenburg
            General Counsel and Secretary


                                       9



