We show how to employ an interference lithographic template (ILT) as a facile mold for fabricating three-dimensional bicontinuous PDMS (poly(dimethylsiloxane)) elastomeric structures and demonstrate the use of such a structure as a mechanically tunable PDMS/air phononic crystal. A positive photoresist was used to make the ILT, and after infiltration with PDMS, the resist was removed in a water-based basic solution which avoided PDMS swelling or pattern collapse occurring during the ILT removal process. Since the period of the structure is approximately 1 microm, the density of states of gigahertz phonons are altered by the phononic PDMS/air crystal. Brillouin light scattering (BLS) was employed to measure phononic modes of the structure as a function of mechanical strain. The results demonstrate that the phononic band diagram of such structures can be tuned mechanically.