Strong light-matter interactions in both the single-emitter and collective strong coupling regimes attract significant attention due to emerging quantum and nonlinear optics applications, as well as opportunities for modifying material-related properties. Further exploration of these phenomena requires an appropriate theoretical methodology, which is demanding since polaritons are at the intersection between quantum optics, solid state physics and quantum chemistry. Fortunately, however, nanoscale polaritons can be realized in small plasmon-molecule systems, which in principle allows treating them using ab initio methods, although this has not been demonstrated to date. Here, we show that time-dependent density-functional theory (TDDFT) calculations can access the physics of nanoscale plasmon-molecule hybrids and predict vacuum Rabi splitting in a system comprising a few-hundred-atom aluminum nanoparticle interacting with one or several benzene molecules. We show that the cavity quantum electrodynamics approach holds down to resonators on the order of a few cubic nanometers, yielding a single-molecule coupling strength exceeding 200 meV due to a massive vacuum field value of 4.5 V/nm. In a broader perspective, our approach enables parameter-free in-depth studies of polaritonic systems, including ground state, chemical and thermodynamic modifications of the molecules in the strong-coupling regime, which may find important use in emerging applications such as cavity enhanced catalysis.