Recently, remarkable advances have been made in coupling a number of high-Q modes of nano-mechanical systems to high-finesse optical cavities, with the goal of reaching regimes where quantum behavior can be observed and leveraged toward new applications. To reach this regime, the coupling between these systems and their thermal environments must be minimized. Here we propose a novel approach to this problem, in which optically levitating a nano-mechanical system can greatly reduce its thermal contact, while simultaneously eliminating dissipation arising from clamping. Through the long coherence times allowed, this approach potentially opens the door to ground-state cooling and coherent manipulation of a single mesoscopic mechanical system or entanglement generation between spatially separate systems, even in room temperature environments. As an example, we show that these goals should be achievable when the mechanical mode consists of the center-of-mass motion of a levitated nanosphere.