Strong lensing is a sensitive probe of the small-scale density fluctuations in the Universe. We implement a novel approach to modeling strongly lensed systems using probabilistic cataloging, which is a transdimensional, hierarchical, and Bayesian framework to sample from a metamodel (union of models with different dimensionality) consistent with observed photon count maps. Probabilistic cataloging allows us to robustly characterize modeling covariances within and across lens models with different numbers of subhalos. Unlike traditional cataloging of subhalos, it does not require model subhalos to improve the goodness of fit above the detection threshold. Instead, it allows the exploitation of all information contained in the photon count maps, for instance, when constraining the subhalo mass function. We further show that, by not including these small subhalos in the lens model, fixed-dimensional inference methods can significantly mismodel the data. Using a simulated Hubble Space Telescope (HST) dataset, we show that the subhalo mass function can be probed even when many subhalos in the sample catalogs are individually below the detection threshold and would be absent in a traditional catalog. With the planned Wide Field Infrared Space Telescope (WFIRST), simultaneous probabilistic cataloging of dark subhalos in high-resolution, deep strong lens images has the potential to constrain the subhalo mass function at even lower masses.