EXHIBIT 23.1 CONSENT OF INDEPENDENT AUDITOR We consent to the incorporation by reference in the Registration Statements (Form S-8 Nos. 33-44137 and 33-44139) pertaining to the Old Dominion Freight Line, Inc. Restricted Stock Agreement and 1991 Employee Stock Option Plan of Old Dominion Freight Line, Inc. of our report dated January 27, 2000, with respect to the consolidated financial statements and schedule of Old Dominion Freight Line, Inc. included in the Annual Report (Form 10-K) for the year ended December 31, 1999. ERNST & YOUNG LLP Winston-Salem, North Carolina March 16, 2000 35