Using cold atoms to simulate strongly interacting quantum systems is an exciting frontier of physics. However, because atoms are nominally neutral point particles, this limits the types of interaction that can be produced. We propose to use the powerful new platform of cold atoms trapped near nanophotonic systems to extend these limits, enabling a novel quantum material in which atomic spin degrees of freedom, motion and photons strongly couple over long distances. In this system, an atom trapped near a photonic crystal seeds a localized, tunable cavity mode around the atomic position. We find that this effective cavity facilitates interactions with other atoms within the cavity length, in a way that can be made robust against realistic imperfections. Finally, we show that such phenomena should be accessible using one-dimensional photonic crystal waveguides in which coupling to atoms has already been experimentally demonstrated.