Structured, periodic optical materials can be used to form photonic crystals capable of dispersing, routing, and trapping light. A similar phenomena in periodic elastic structures can be used to manipulate mechanical vibrations. Here we present the design and experimental realization of strongly coupled optical and mechanical modes in a planar, periodic nanostructure on a silicon chip. 200-Terahertz photons are co-localized with mechanical modes of Gigahertz frequency and 100-femtogram mass. The effective coupling length, which describes the strength of the photon-phonon interaction, is as small as 2.9 microns, which, together with minute oscillator mass, allows all-optical actuation and transduction of nanomechanical motion with near quantum-limited sensitivity. Optomechanical crystals have many potential applications, from RF-over-optical communication to the study of quantum effects in mesoscopic mechanical systems.