We present the design, fabrication and initial characterization of a paddle nanocavity consisting of a suspended sub-picogram nanomechanical resonator optomechanically coupled to a photonic crystal nanocavity. The optical and mechanical properties of the paddle nanocavity can be systematically designed and optimized, and key characteristics including mechanical frequency easily tailored. Measurements under ambient conditions of a silicon paddle nanocavity demonstrate an optical mode with quality factor $Q_o$ ~ 6000 near 1550 nm, and optomechanical coupling to several mechanical resonances with frequencies $omega_m/2pi$ ~ 12-64 MHz, effective masses $m_text{eff}$ ~ 350-650 fg, and mechanical quality factors $Q_m$ ~ 44-327. Paddle nanocavities are promising for optomechanical sensing and nonlinear optomechanics experiments.