We present a methodology for fast band-structure calculations that is generally applicable to problems of elastic wave propagation in periodic media. The methodology, called Bloch mode synthesis, represents an extension of component mode synthesis, a set of substructuring techniques originally developed for structural dynamics analysis. In Bloch mode synthesis, the unit cell is divided into interior and boundary degrees-of-freedom, which are described, respectively, by a set of normal modes and a set of constraint modes. A combination of these mode sets then forms a reduced basis for the band structure eigenvalue problem. The reduction is demonstrated on a phononic-crystal model and a locally resonant elastic-metamaterial model and is shown to accurately predict the frequencies and Bloch mode shapes with a dramatic decrease in computation time in excess of two orders of magnitude.