The effects of cavity quantum electrodynamics (QED), caused by the interaction of matter and the electromagnetic field in subwavelength resonant structures, have been the subject of intense research in recent years(1). The generation of coherent radiation by subwavelength resonant structures has attracted considerable interest, not only as a means of exploring the QED effects that emerge at small volume, but also for its potential in applications ranging from on-chip optical communication to ultrahigh-resolution and high-throughput imaging, sensing and spectroscopy. One such strand of research is aimed at developing the 'ultimate' nanolaser: a scalable, low-threshold, efficient source of radiation that operates at room temperature and occupies a small volume on a chip(2). Different resonators have been proposed for the realization of such a nanolaser-microdisk(3) and photonic bandgap(4) resonators, and, more recently, metallic(5,6), metallodielectric(7-10) and plasmonic(11,12) resonators. But progress towards realizing the ultimate nanolaser has been hindered by the lack of a systematic approach to scaling down the size of the laser cavity without significantly increasing the threshold power required for lasing. Here we describe a family of coaxial nanostructured cavities that potentially solve the resonator scalability challenge by means of their geometry and metal composition. Using these coaxial nanocavities, we demonstrate the smallest room-temperature, continuous-wave telecommunications-frequency laser to date. In addition, by further modifying the design of these coaxial nanocavities, we achieve thresholdless lasing with a broadband gain medium. In addition to enabling laser applications, these nanoscale resonators should provide a powerful platform for the development of other QED devices and metamaterials in which atom-field interactions generate new functionalities(13,14).