We consider the problem of distributing a vaccine for immunizing a scale-free network against a given virus or worm. We introduce a method, based on vaccine dissemination, that seems to reflect more accurately what is expected to occur in real-world networks. Also, since the dissemination is performed using only local information, the method can be easily employed in practice. Using a random-graph framework, we analyze our method both mathematically and by means of simulations. We demonstrate its efficacy regarding the trade-off between the expected number of nodes that receive the vaccine and the network’s resulting vulnerability to develop an epidemic as the virus or worm attempts to infect one of its nodes. For some scenarios, the method is seen to render the network practically invulnerable to attacks while requiring only a small fraction of the nodes to receive the vaccine.