Centroidal Voronoi tessellations (CVTs) are Voronoi tessellations whose generators coincide with the mass centroids of the respective Voronoi regions. CVTs have become useful tools in many application domains of arts, sciences and engineering. In this work, for the first time the concept of the periodic centroidal Voronoi tessellations (PCVTs) — CVTs that exhibit certain periodicity properties in the Euclidean space — is introduced and given a rigorous treatment. We discuss the basic mathematical structures of the PCVTs and show how they are related to the so-called CVT clustering energy. We demonstrate by means of a concrete example that the clustering energy can lose smoothness at degenerate points which disproves earlier conjectures about the CVT energy being globally $C^2$-smooth. We discuss a number of algorithms for the computation of PCVTs, including modifications of the celebrated Lloyd algorithm and a recently developed algorithm based on the shrinking dimer dynamics for saddle point search. As an application, we present a catalog of numerically computed PCVT patterns for the two dimensional case with a constant density and a square unit cell. Examples are given to demonstrate that our algorithms are capable of effectively probing the energy surface and produce improved patterns that may be used for optimal materials design. The numerical results also illustrate the intrinsic complexity associated with the CVT energy landscape and the rich geometry and symmetry represented by the underlying PCVTs.