We present the R package mnlogit for estimating multinomial logistic regression models, particularly those involving a large number of categories and variables. Compared to existing software, mnlogit offers speedups of 10-50 times for modestly sized problems and more than 100 times for larger problems. Running in parallel mode on a multicore machine gives up to 4 times additional speedup on 8 processor cores. mnlogit achieves its computational efficiency by drastically speeding up computation of the log-likelihood function's Hessian matrix through exploiting structure in matrices that arise in intermediate calculations. This efficient exploitation of intermediate data structures allows mnlogit to utilize system memory much more efficiently, such that for most applications mnlogit requires less memory than comparable software by a factor that is proportional to the number of model categories.