In this paper, we present a theoretical analysis of the propagation of acoustic waves through elastic and viscoelastic two-dimensional phononic crystal structures. Numerical calculations of transmission spectra are conducted by extending the finite-difference-time-domain method to account for linear viscoelastic materials with time-dependent moduli. We study a phononic crystal constituted of a square array of cylindrical air inclusions in a solid viscoelastic matrix. The elastic properties of the solid are those of a silicone rubber. This system exhibits very wide band gaps in its transmission spectrum that extend to frequencies in the audible range of the spectrum. These gaps are characteristic of fluid matrix/air inclusion systems and result from the very large contrast between the longitudinal and transverse speeds of sound in rubber. By treating the matrix as a viscoelastic medium within the standard linear solid (SLS) model, we demonstrate that viscoelasticity impacts the transmission properties of the rubber/air phononic crystal not only by attenuating the transmitted acoustic waves but also by shifting the passing bands frequencies toward lower values. The ranges of frequencies exhibiting attenuation or frequency shift are determined by the value of the relaxation time in the SLS model. We show that viscoelasticity can be used to decrease the frequency of pass bands (and consequently stop bands) in viscoelastic/air phononic crystals.