Homelessness is a complex and persistent societal challenge that requires innovative thinking in order to design solutions that not only provide immediate relief but also address the problem holistically. In this work, we introduce a probabilistic agent-based model of the homeless service system (PATHS) in our effort to develop a virtual laboratory that will eventually serve as a testbed for policy interventions and a tool for the ethical study of homelessness. PATHS is designed to simulate the movement of individuals through the unobserved network of homeless services while at the same time capturing system-level population dynamics by incorporating practical constraints such as capacity limits, time-dependent entry rates, and transition bottlenecks. Our experimental evaluation shows that PATHS closely matches the characteristics of service navigation in a real-world dataset, despite its simplicity, and outperforms baseline models, often by a considerable margin.