We theoretically study the coupling of Bose-Einstein condensed atoms to the mechanical oscillations of a nanoscale cantilever with a magnetic tip. This is an experimentally viable hybrid quantum system which allows one to explore the interface of quantum optics and condensed matter physics. We propose an experiment where easily detectable atomic spin-flips are induced by the cantilever motion. This can be used to probe thermal oscillations of the cantilever with the atoms. At low cantilever temperatures, as realized in recent experiments, back-action of the atoms onto the cantilever is significant and the system represents a mechanical analog of cavity quantum electrodynamics. With high but realistic cantilever quality factors, the strong coupling regime can be reached, either with single atoms or collectively with BECs. We discuss an implementation on an atom chip.