In Hurricane Katrina's aftermath, several hundred thousand former residents of New Orleans and the Gulf Coast lost their jobs. In this paper we review some of the short- and longer-term challenges and uncertainties involved in tackling labor market issues in rebuilding New Orleans. We also present some policy proposals for addressing them. The needs of those returning to New Orleans, as well as those who choose to remain or go elsewhere, are considered. We argue that, for fairly modest public expenditures, the labor market disadvantages of many current and former residents can be addressed and their long-term employment outcomes improved.