We analyze the performance of a quantum repeater protocol based on single trapped ions. At each node, single trapped ions embedded into high-finesse cavities emit single photons whose polarization is entangled with the ion state. A specific detection of two photons at a central station located half-way between two nodes heralds the entanglement of two remote ions. Entanglement can be extended to long distances by applying successive entanglement swapping operations based on two-ion gate operations that have already been demonstrated experimentally with high precision. Our calculation shows that the distribution rate of entanglement achievable with such an ion-based quantum repeater protocol is higher by orders of magnitude than the rates that are achievable with the best known schemes based on atomic-ensemble memories and linear optics. The main reason is that for trapped ions the entanglement swapping operations are performed deterministically, in contrast to success probabilities below 50% per swapping with linear optics. The scheme requires efficient collection of the emitted photons, which can be achieved with cavities, and efficient conversion of their wavelength, which can be done via stimulated parametric down-conversion. We also suggest how to realize temporal multiplexing, which offers additional significant speed ups in entanglement distribution, with trapped ions.