Muller's ratchet is an evolutionary process that has been implicated in the extinction of asexual species, the evolution of non-recombining genomes, such as the mitochondria, the degeneration of the Y chromosome, and the evolution of sex and recombination. Here we study the speed of Muller's ratchet in a spatially structured population which is subdivided into many small populations (demes) connected by migration, and distributed on a graph. We studied different types of networks: regular networks (similar to the stepping-stone model), small-world networks and completely random graphs. We show that at the onset of the small-world network – which is characterized by high local connectivity among the demes but low average path length – the speed of the ratchet starts to decrease dramatically. This result is independent of the number of demes considered, but is more pronounced the larger the network and the stronger the deleterious effect of mutations. Furthermore, although the ratchet slows down with increasing migration between demes, the observed decrease in speed is smaller in the stepping-stone model than in small-world networks. As migration rate increases, the structured populations approach, but never reach, the result in the corresponding panmictic population with the same number of individuals. Since small-world networks have been shown to describe well the real contact networks among people, we discuss our results in the light of the evolution of microbes and disease epidemics.