Chemical reactions at ultralow temperatures are of fundamental importance to primordial molecular evolution as it occurs on icy mantles of dust nanoparticles or on ultracold water clusters in dense interstellar clouds. As we show, studying reactions in a stepwise manner in ultracold helium nanodroplets by mass-selective infrared (IR) spectroscopy provides an avenue to mimic these "stardust conditions" in the laboratory. In our joint experimental/theoretical study, in which we successively add H2O molecules to HCl, we disclose a unique IR fingerprint at 1337 cm-1 that heralds hydronium (H3O+) formation and, thus, acid dissociation generating solvated protons. In stark contrast, no reaction is observed when reversing the sequence by allowing HCl to interact with preformed small embryonic ice-like clusters. Our ab initio simulations demonstrate that not only reaction stoichiometry but also the reaction sequence needs to be explicitly considered to rationalize ultracold chemistry.