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 and opportunities for modifying material-related properties. Exploration of these phenomena is theoretically demanding, as polaritons exist at the intersection between quantum optics, solid state physics, and quantum chemistry. Fortunately, nanoscale polaritons can be realized in small plasmon-molecule systems, enabling treatment with ab initio methods. Here, we show that time-dependent density-functional theory calculations access the physics of nanoscale plasmon-molecule hybrids and predict vacuum Rabi splitting. By considering a system comprising a few-hundred-atom aluminum nanoparticle interacting with benzene molecules, we show that cavity quantum electrodynamics holds down to resonators of a few cubic nanometers in size, yielding a single-molecule coupling strength exceeding 200 meV due to a massive vacuum field of 4.5 V/nm. In a broader perspective, ab initio methods enable parameter-free in-depth studies of polaritonic systems for emerging applications.