We present an algorithm to compute a primary decomposition of an ideal in a polynomial ring over the integers. For this purpose we use algorithms for primary decomposition in polynomial rings over the rationals, resp. over finite fields, and the idea of Shimoyama-Yokoyama, resp. Eisenbud-Hunecke-Vasconcelos, to extract primary ideals from pseudo-primary ideals. A parallelized version of the algorithm is implemented in Singular. Examples and timings are given at the end of the article.