QuickLinks -- Click here to rapidly navigate through this document

Exhibit 10.31

EIGHTH AMENDMENT TO
LOAN AGREEMENT

        EIGHTH AMENDMENT dated as of October 2, 2001 (the "Amendment"), to the LOAN AGREEMENT dated as of November 19, 1999, as amended by the First Amendment, dated as of February 16, 2000, as further amended by the Second Amendment, dated as of April 14, 2000, as further amended by the Third Amendment, dated June 23, 2000, as further amended by the Fourth Amendment, dated October 11, 2000, as further amended by the Fifth Amendment, dated January 10, 2001, as further amended by the Sixth Amendment, dated April 2, 2001, and as further amended by the Seventh Amendment, dated July 10, 2001 (as so amended, the "Agreement"), among Allied Worldwide, Inc., formerly known as NA Holding Corporation (the "Company"), Blue Ridge Investments, LLC ("Blue Ridge") and Chase Securities, Inc. ("Chase" and, together with Blue Ridge and Chase's and Blue Ridge's respective permitted successors and assigns under the Agreement, the "Lenders").

        WHEREAS, the Company and the Lenders have entered into the Agreement;

        WHEREAS, the Company and the Lenders wish to amend certain provisions of the Agreement pursuant to Section 9.2 of the Agreement;

        NOW, THEREFORE, the Company and the Lenders hereby amend the Agreement as follows:

        1.     Capitalized terms used in this Amendment without definition shall have the meanings given to them in the Agreement.

        2.     The first paragraph of Section 3.5(a) of the Agreement is amended to read in its entirety as follows:

        (a)   On any Business Day on or after December 1, 1999 and prior to the date that is 780 days after the Issue Date, all (but not less than all) of the Lenders may elect to exchange all (but not less than all) of the Loan for one or more Exchange Notes by giving not less than five Business Days' prior irrevocable written notice of such election to the Borrower and the Trustee specifying the name of each proposed registered holder and, subject to the terms of the Indenture, the amount of each Exchange Note requested (each such notice, an "Exchange Notice").

        3.     Section 3.5(e) of the Agreement is amended to read in its entirety as follows:

        (e)   On the day that is 780 days after the Issue Date, the Lenders shall be deemed to have delivered an Exchange Notice and to have made all the agreements and representations required by Section 3.5(a). The Loan shall thereupon be exchanged for Exchange Notes as and when provided in this Section 3.5.

        4.     Each of the undersigned, by its signature below, gives its written consent to this Amendment, and on and after the date first written above, each reference to the Agreement shall mean and be a reference to the Agreement as amended and modified by this Amendment, unless the context otherwise requires.

        5.     This Amendment shall be effective as of the date first above written, and, except as set forth herein, the Agreement shall remain in full force and effect and shall be otherwise unaffected hereby.

        6.     This Amendment may be executed in two or more counterparts, each of which shall be deemed to be an original, but all of which together shall constitute one and the same instrument.

        7.     This Amendment and the rights and obligations of the parties under this agreement shall be governed by, and construed and interpreted in accordance with, the law of the State of New York.

1

        IN WITNESS WHEREOF, the parties hereto have caused this Amendment to be duly executed and delivered by their proper and duly authorized officers as of the day and year first above written.

ALLIED WORLDWIDE, INC.
By:	/s/  RON MILEWSKI
	Name:	Ron Milewski
	Title:	Senior Vice President and Chief Financial Officer
BLUE RIDGE INVESTMENTS LLC
By:	/s/  THOMAS G. WHITE
	Name:	Thomas G. White
	Title:	Managing Director
CHASE SECURITIES INC.
By:	/s/  BENJAMIN BEN-ATTAR
	Name:	Benjamin Ben-Attar
	Title:	Vice President

2

QuickLinks

Exhibit 10.31

EIGHTH AMENDMENT TO LOAN AGREEMENT