This paper develops and implements an analytical framework for estimating optimal taxes on the fuel use and mileage of heavy-duty trucks, accounting for external costs from congestion, accidents, pavement damage, noise, energy security, and local and global pollution. The analysis allows for endogenous fuel economy, increased auto travel (and externalities) in response to reduced truck congestion, and it distinguishes driving by truck type and region. We estimate the optimal (second-best) diesel fuel tax is $1.12 per gallon, and implementing it increases welfare by $1.34 billion per annum. However, optimizing over both fuel and mileage taxes, and differentiating mileage taxes by vehicle type and region, yields progressively higher welfare gains. The most efficient tax structure involves a diesel fuel tax of 69 cents per gallon and charges on trucks that vary between 7 and 20 cents per mile; implementing this tax structure yields welfare gains of $2.06 billion.