Bacterial insertion sequences are the simplest form of autonomous mobile DNA. It is unknown whether they need to have beneficial effects to infect and persist in bacterial populations, or whether horizontal gene transfer suffices for their persistence. We address this question by using branching process models to investigate the critical, early phase of an insertion sequence infection. We find that the probability of a successful infection is low and depends linearly on the difference between the rate of horizontal gene transfer and the fitness cost of the insertion sequences. Our models show that the median time to extinction of an insertion sequence that dies out is very short, while the median time for a successful infection to reach a modest population size is very long. We conclude that horizontal gene transfer is strong enough to allow the persistence of insertion sequences, although infection is an erratic and slow process.