We propose and analyze a setup to achieve strong coupling between a single trapped atom and a mechanical oscillator. The interaction between the motion of the atom and the mechanical oscillator is mediated by a quantized light field in a laser driven high-finesse cavity. In particular, we show that high fidelity transfer of quantum states between the atom and the mechanical oscillator is in reach for existing or near future experimental parameters. Our setup provides the basic toolbox for coherent manipulation, preparation and measurement of micro- and nanomechanical oscillators via the tools of atomic physics.