Most models of neural associative memory have used networks with broad connectivity. However, from both a neurobiological viewpoint and an implementation perspective, it is logical to minimize the length of inter-neural connections and consider networks whose connectivity is predominantly local. The “small-world networks” model described recently by Watts and Strogatz provides an interesting approach to this issue. In this paper, we show that associative memory networks with small-world architectures can provide the same retrieval performance as randomly connected networks while using a fraction of the total connection length.