Naive T cells have long been thought to recirculate exclusively between secondary lymphoid organs via the lymph and blood. Evidence is now emerging that this view may be too simplistic and that naive T cells routinely traffic through non-lymphoid organs in a manner similar to that of memory T cells, albeit in lower numbers. This represents a fundamental shift in the current paradigm of T-cell migration through different types of tissue. This review summarizes these recent findings, along with the similarities and differences in migratory properties of naive and memory T cells, and discusses how and why naive T cells might access non-lymphoid tissues.