As nanofabrication techniques become more precise, with ever smaller feature sizes, the ability to model nonlocal effects in plasmonics becomes increasingly important. While nonlocal models based on hydrodynamics have been implemented using various computational electromagnetics techniques, the finite-difference time-domain (FDTD) version has remained elusive. Here we present a comprehensive FDTD implementation of nonlocal hydrodynamics, including for parallel computing. As a sub-nanometer step size is required to resolve nonlocal effects, a parallel implementation makes the computational cost of nonlocal FDTD more affordable. We first validate our algorithms for small spherical metallic particles, and find that nonlocality smears out staircasing artifacts at metal surfaces, increasing the accuracy over local models. We find this also for a larger nanostructure with sharp extrusions. The large size of this simulation, where nonlocal effects are clearly present, highlights the importance and impact of a parallel implementation in FDTD. CCBY