SERIES A CONVERTIBLE SUBORDINATED DEBENTURE PURCHASE AGREEMENT

EXHIBIT 10.12

SERIES A CONVERTIBLE SUBORDINATED DEBENTURE PURCHASE AGREEMENT

THIS SERIES A CONVERTIBLE SUBORDINATED DEBENTURE PURCHASE AGREEMENT (this “Agreement”) is made and entered into this 3rd day of July, 2006, by and between VELOCITY EXPRESS CORPORATION, a Delaware corporation (the “Buyer”) and each of the parties listed as Sellers on Exhibit “A” attached hereto (hereafter each referred to as a “Seller” and collectively referred to as the “Sellers”).

W I T N E S S E T H:

WHEREAS, each Seller holds a certain Series A Convertible Subordinated Debenture in the principal amount specified opposite such Seller’s name on Exhibit “A” annexed hereto (hereafter each referred to as a “Note” and collectively referred to as the “Notes”) which is convertible into shares of Common Stock of CD&L, Inc., a Delaware corporation (the “Company”); and

WHEREAS, Sellers are willing and desire to sell all of the Notes to Buyer, and Buyer is willing and desires to purchase and acquire the Notes from Sellers, all upon the terms and conditions hereinafter set forth; and

WHEREAS, prior to the Closing (as defined below), the Company will have paid all of the accrued but unpaid interest on the Notes through the Closing Date to the Sellers; and

WHEREAS, prior to the execution and delivery of this Agreement, the Board of Directors of the Company has taken all actions required to: (a) approve the execution and delivery of that certain Agreement and Plan of Merger of even date herewith, by and between the Company, Buyer and CD&L Acquisition Corp., a Delaware corporation (the “Merger Agreement”); (b) prevent any right issued pursuant to that certain Stockholder Protection Rights Agreement, dated as of December 27, 1999 between the Company and American Stock Transfer & Trust Company, as Rights Agent, and amended as of April 14, 2004 (the “Stockholder Protection Rights Agreement”) from being exercisable pursuant to the Stockholder Protection Rights Agreement as a result of the transactions contemplated herein and under the Merger Agreement; (c) prevent any Separation Time (as such term is defined in the Stockholder Protection Rights Agreement) from occurring as a result of the transactions contemplated herein or under the Merger Agreement; (d) waive the applicability of Section 203 of the Delaware General Corporation Law with respect to the Company and the transactions contemplated herein and under the Merger Agreement; and (e) subject to any restrictions on the exercise of any rights that Velocity may have under the Loan Agreement (as defined below) as provided under the Merger Agreement, consent to the assignment of each Seller’s rights as Lender under that certain Amended and Restated Senior Subordinated Loan Agreement dated as of April 14, 2004 by and among the Sellers, the Company, and certain other stockholders of the Company (the “Loan Agreement”) to Velocity; and (f) waive any and all rights the Company may have under that certain Restructuring and Exchange Agreement dated as of April 14, 2004 by and among the Company, Exeter Venture Lenders, L.P. (“Exeter Venture”), the Investors (as defined below)

and the individuals listed therein as “Investors” (the “Restructuring Agreement”) which would restrict, prevent or inhibit the consummation of the transactions contemplated under this Agreement, including, without limitation, any obligation of the Holders to provide an opinion of counsel under Section 6.9 of the Restructuring Agreement with respect to the transactions contemplated in this Agreement; and

WHEREAS, prior to the execution and delivery of this Agreement, Exeter Capital Partners IV, L.P. and BNP Paribas (each being referred to herein as an “Investor” and collectively as the “Investors”) have (a) consented to the sale and transfer of the Notes from the Sellers to Buyer, as contemplated by this Agreement, and (b) waived any and all rights of co-sale which the Investors may have in connection with the transactions contemplated hereunder pursuant to that certain Stockholders Agreement dated April 14, 2004 by and among the Company, the Sellers and the Investors (the “Stockholders Agreement”) including, without limitation, any rights of co-sale under Section 2.1 of the Stockholders Agreement; and

WHEREAS, prior to the execution and delivery of this Agreement, each Seller and each Investor has waived any and all rights of first refusal each Seller or Investor may have in connection with the transactions contemplated hereunder pursuant to the Stockholders Agreement, including, without limitation, all rights of first refusal provided for under Section 3.1 of the Stockholders Agreement.

NOW, THEREFORE, in consideration of the mutual covenants hereinafter contained and the payment of good and valuable consideration, the receipt and sufficiency of which is hereby acknowledged by each of the parties hereto, it is agreed as follows:

1. Purchase of Notes; Purchase Price. Subject to the terms and conditions hereinafter set forth, at the Closing, Sellers shall assign, transfer and deliver to Buyer, and Buyer shall purchase and acquire from Sellers, all of Sellers’ right, title and interest in and to all the Notes for a purchase price of $3.25 per share of Common Stock of the Company into which each Note is convertible, for an aggregate purchase price of $12,795,275.59 (the “Purchase Price”) as full consideration for the purchase of the Notes. The purchase price to be paid to each Seller shall be the allocated among and between the Sellers in the respective amounts specified opposite such Seller’s name on Exhibit “A” annexed hereto. In furtherance of the foregoing, each Seller shall deliver to Buyer the instrument of transfer, substantially in the form of Exhibit “B”, attached hereto and incorporated herein by this reference (the “Assignment”), duly executed to effect this transaction.

2. Closing.

(a) Closing. The closing (the “Closing”) of the transactions contemplated under this Agreement shall take place upon execution and delivery of this Agreement and each document or instrument to be delivered hereunder by each of the parties hereto and delivery by Buyer of the Purchase Price to each Seller and the simultaneous execution and delivery of the Merger Agreement and funding of the Paying Agent with the Merger Consideration as required thereunder (the “Closing Date”).

2

(b) Closing Deliveries. At Closing, each Seller (or with respect to the Voting Agreement (as defined below), such Sellers who are a party thereto) shall deliver to the Buyer the following:

(i) an executed original of this Agreement;

(ii) an executed original of the Voting Agreement; and

(ii) the original Note (or in the event that the original Note is lost or destroyed, an affidavit of lost security with respect to such Seller’s Note), together with the fully-executed Assignment.

(c) At Closing, Buyer shall deliver to each Seller (or with respect to the Voting Agreement, such Sellers who are a party thereto) the following:

(i) an executed original of this Agreement;

(ii) an executed original of the Voting Agreement; and

(iii) the Purchase Price for such Seller’s Note (as set forth in Exhibit “A”), payable by wire transfer to an account designated by each Seller.

3. Condition Precedent to Closing. In addition to any other condition provided for herein, the obligation of Buyer to buy the Notes, as provided for under this Agreement, is subject to the delivery at Closing of an executed original of that certain Voting Agreement in the form annexed hereto as Exhibit “C” (the “Voting Agreement”) by each of the Sellers listed on the signature page to the Voting Agreement, whereby such Sellers have agreed to vote all of the shares of Common Stock of the Company owned by them in accordance with the terms and conditions of the Voting Agreement.

4. Assignment of Rights Under Accompanying Agreements. By execution and delivery of this Agreement, each Seller hereby grants, assigns and transfers to Buyer at Closing each Seller’s full right, title and interest in and to: (a) the Stockholders Agreement; (b) that certain Registration Rights Agreement dated as of April 14, 2004 by and between the Company and such Seller (the “Registration Rights Agreement”); and (c) the Loan Agreement (collectively, the “Accompanying Agreements”). Buyer hereby assumes all of the obligations of Seller pursuant to the Accompanying Agreements.

5. Representations and Warranties.

5.1 Each Seller hereby severally and not jointly, represents and warrants to Buyer that:

(a) each Seller is the sole owner of the respective Note issued to and currently held by each Seller and which is to be delivered to Buyer in accordance with this Agreement;

3

(b) subject to the waivers and consents that have been obtained as provided in the recitals to this Agreement, the Note held by Seller is freely transferable and assignable and each Seller has good, absolute and marketable title to the respective Note issued to and currently held by each Seller, free and clear of all liens, claims, encumbrances, options and restrictions of every kind and has the unrestricted right to sell and transfer the Note and upon execution and delivery of the Assignment to Buyer, Buyer will have good and marketable title to the Note, free and clear of all liens;

(c) subject to the consents and waivers that have been obtained as provided in the recitals to this Agreement, each Seller has the full right, power, legal capacity and authority to execute this Agreement and to perform all of the agreements, undertakings, covenants, representations and warranties herein contained and to assign to Buyer the Seller’s interest in the Accompanying Agreements;

(d) the execution of this Agreement and the delivery of the Notes by the Sellers and the performance by each Seller of their respective obligations hereunder and the consummation by each Seller of the transactions contemplated by this Agreement will not: (i) contravene any provision of the Certificate of Incorporation, By-Laws or other governing document of the Company; or (ii) conflict with, result in any breach of, or constitute a default (or an event which would, with the passage of time or the giving of notice or both, constitute a default) under, or give rise to a right to terminate, amend, modify, abandon or accelerate, any contract or agreement which is applicable to, binding upon or enforceable against the Company or any Seller;

(e) this Agreement has been duly executed and delivered by each Seller and constitutes each Seller’s legal, binding and enforceable obligation, subject to bankruptcy, insolvency, reorganization and other laws affecting creditors rights generally, and subject to remedies, the enforcement of which vests in the discretion of courts of equitable jurisdiction; and

(f) each Seller who is an officer or director of the Company and is subject to the reporting and short-swing liability provisions of Section 16 of the Securities Exchange Act of 1934 (the “Exchange Act”) hereby, severally and not jointly, represents and warrants to Buyer that (i) such Seller has not acquired any securities of the Company within the six (6) month period ending on the date of this Agreement, (ii) the consummation of the transactions set forth herein by such Seller will not result in a nonexempt short-swing transaction under Section 16 of the Exchange Act with respect to such Seller, and (iii) consummation of the transactions set forth herein by such Seller will not result in liability under Section 16(b) of the Exchange Act to any Seller, the Buyer or the Company.

5.2 Buyer hereby represents and warrants to each Seller that Buyer has full power and authority to enter into this Agreement; this Agreement constitutes a valid and legally

4

binding obligation of Buyer, enforceable in accordance with its terms, except as same may be limited by applicable bankruptcy, insolvency, reorganization, management, moratorium or other similar laws affecting creditors’ rights and subject to general equity principles and to limitations on availability of equitable relief.

6. Miscellaneous.

6.1 Notice.

(a) Any notice or other communication required or permitted hereunder shall be in writing and shall be deemed to have been duly given on (i) the date of service if served personally; (ii) three (3) business days after the date of mailing, if mailed by first class mail, registered or certified, postage prepaid, return receipt requested; or (iii) one (1) business day after delivery to the courier if sent by private courier guaranteeing next day delivery, delivery charges prepaid.

(b) Notices shall be sent to the following addresses: (i) if to Buyer, to One Morningside Drive North, Building B, Suite 300, Westport, Connecticut, 06880, Attention: General Counsel, or such other address as may hereafter be designated in writing by Buyer, with a copy to Budd Larner, P.C., 150 John F. Kennedy Parkway, Short Hills, New Jersey 07078, Attn: James F. Fitzsimmons, Esq.; and (ii) if to Sellers, to their respective addresses set forth on Exhibit A hereto, or such other address as may hereafter be designated in writing by the applicable Seller.

6.2 Severability. The invalidity of any provision of this Agreement, or part thereof, shall not affect the validity or enforceability of the remainder of such provision and/or this Agreement.

6.3. Benefit. All the terms and provisions hereof shall inure to the benefit of and be binding upon the successors and assigns of the Buyer and the respective successors and assigns of each Seller.

6.4. Counterparts; Facsimile Signatures. This Agreement may be executed in one or more counterparts, each of which shall be deemed to be an original, and all of which together shall be deemed to constitute one and the same Agreement. A facsimile signature to this Agreement of any party shall be considered to have the same binding legal effect as an original signature

6.5. Headings. The headings of the paragraphs of this Agreement are for convenience and reference only and do not constitute a part of this Agreement and in no way modify, interpret or construe the understanding of the parties hereto.

6.6. Governing Law; Jurisdiction.

(a) This Agreement and the rights and obligations of the parties hereunder shall be construed and enforced in accordance with the laws of the State of Delaware, without giving effect to the principles of conflicts of law thereof.

5

(b) Each party to this Agreement irrevocably consents and agrees that any legal action or proceeding with respect to this Agreement and any action for enforcement of any judgment in respect thereof will be brought in the federal or state courts located within the jurisdiction of the United Stated District Court for the Southern District of New York, and, by execution and delivery of this Agreement, each party to this Agreement irrevocably submits to and accepts for itself and in respect of its property, generally and unconditionally, the exclusive jurisdiction of the aforesaid courts and appellate courts from any appeal thereof. Each party to this Agreement further irrevocably consents to the service of process out of any of the aforesaid courts in any such action or proceeding by the mailing of copies thereof in the manner set forth in Section 6.1 hereof. Each party to this Agreement hereby irrevocably waives any objection which it may now have or hereafter have to the laying of venue of any of the aforesaid actions or proceedings arising out of or in connection with this Agreement brought in any of the courts referred to above and hereby further irrevocably waives and agrees not to plead or claim in any such court that any such action or proceeding brought in any such court is an inconvenient forum. Nothing in this Section shall be deemed to constitute a submission to jurisdiction, consent or waiver with respect to any matter not specifically referred to herein.

6.7. Entire Agreement. This Agreement and the Voting Agreement (to the extent a Seller is a party thereto) constitute the entire understanding between the parties hereto with respect to the subject matter hereof and may not be changed, nor modified orally, but only by the amendment to the Agreement in writing, signed by the party against whom enforcement of any change or modification in sought.

6.8. Integration. This Agreement and the Voting Agreement (to the extent a Seller is a party thereto) supersede all prior agreements and understandings among the parties to this Agreement with respect to the subject matter hereof and contains the full understanding of the parties hereto with respect to the subject matter hereof; and there are no representations, warranties, agreements or undertakings other than expressly contained herein or therein.

6.9. Further Assurances. Each Seller agrees that he will do such further acts and things and execute and deliver to Buyer such additional conveyances, assignments, agreements and instruments as Buyer may require or deem advisable to carry into effect the purpose of this Agreement.

6.10 Interpretation. In all references herein to any parties, persons, entities or corporations, the use of any particular gender or the plural or singular number is intended to include the appropriate gender or number as the text of the within instrument may require

6.11 Modification. This Agreement may be modified or amended only by a written instrument duly signed by all of the parties hereto or their respective successors or assigns.

6.12 Assignments and Successors. No party may assign any of its rights under this Agreement without the prior written consent of the other parties to this Agreement. Subject to the preceding sentence, this Agreement will apply to, be binding in all respects upon, and inure to the benefit of the successors and permitted assigns of the parties.

6

6.13 Benefits Only to Parties. Nothing expressed by or mentioned in this Agreement is intended or shall be construed to give any person other than the parties hereto and their respective successors and permitted assigns any legal or equitable right, remedy or claim under or in respect of this Agreement or any provision herein contained, this Agreement and all conditions and provisions hereof being intended to be and being for the sole and exclusive benefit of the parties hereto and their respective successors and permitted assigns; provided, however, that to the extent that the Company has any rights under the Notes and the Accompany Agreements, the Company shall be a third party beneficiary of this Agreement.

6.14 Waiver of Trial by Jury. EACH OF THE PARTIES HERETO, TO THE EXTENT PERMITTED BY APPLICABLE LAW, HEREBY IRREVOCABLY WAIVES ALL RIGHT OF TRIAL BY JURY IN ANY ACTION, PROCEEDING OR COUNTERCLAIM, ARISING OUT OF OR IN CONNECTION WITH THIS AGREEMENT OR ANY MATTER ARISING HEREUNDER.

6.15 Recitals. The recitals to this Agreement are incorporated herein by this reference and shall be construed as if they are a part of this Agreement.

[SIGNATURE PAGE FOLLOWS]

7

IN WITNESS WHEREOF, the Buyer and each Seller has executed this Note Purchase Agreement as of the date first above written.

[Signature Page to Debenture Purchase Agreement]

8

[Signature Page to Debenture Purchase Agreement]

9

EXHIBIT “A”

10

EXHIBIT “B”

Form of Assignment

THIS ASSIGNMENT (the “Assignment”) by and between VELOCITY EXPRESS CORPORATION, a Delaware corporation (the “Assignee”) and the undersigned Assignor is effective as of the              day of June, 2006. Reference is hereby made to that certain Series A Convertible Note Purchase Agreement of even date herewith by and among the Assignee, as Buyer and the Assignor, as a Seller (the “Note Purchase Agreement”). All capitalized terms not defined herein shall have the meaning ascribed to it in the Note Purchase Agreement.

FOR VALUE RECEIVED, Assignor hereby grants, transfers and assigns to Assignee all of his respective right, title and interest in and to the respective Note held and owned by him, as specified below, including, without limitation all rights, title and interest: (i) to convert such Note into shares of Common Stock as provided within the Note, together with any rights that may attach thereto pursuant to the Stockholder Protection Rights Agreement; (ii) under the Stockholders Agreement; (iii) under the Registration Rights Agreement; and (iv) under the Loan Agreement and Assignee hereby accepts such assignment. This Assignment arises out of the Note Purchase Agreement, the applicable terms and conditions of which are hereby incorporated herein by this reference.

This Assignment shall be binding upon and inure to the benefit of the Assignor and Assignee and their respective successors and assigns. This Assignment may be executed in one or more counterparts, each of which shall be deemed to be an original, and all of which together shall be deemed to constitute one and the same Assignment. A facsimile signature to this Assignment of any party shall be considered to have the same binding legal effect as an original signature hereto.

Signature Page to Assignment (Exhibit B to Debenture Purchase Agreement)

11

EXHIBIT “C”

Voting Agreement

12