PT-symmetry, invariance under the combined operations of spatial reflection and time reversal, arises naturally in non-Hermitian physics and has been attracting an increasing amount of attention in the literature. Here, we examine probabilistic structures within the unbroken and broken PT-symmetric regimes from a C*-algebraic perspective. We show that PT-unbroken probability is directly compatible with the operator-algebraic formulation of standard QM. However, though PT-broken Hamiltonians may generate well-defined non-unitary dynamics, basic structural properties required for quantum probability typically fail. We analyze this failure via relation to the GNS construction, ultimately demonstrating that an extension to a C*-algebraic probability theory on a Hermitian supersystem is required to define a meaningful probability calculus within the PT-broken system itself. Thereby, consistent probability assignment must be extrinsic to the PT-broken phase, and must be inherited from a dilation to a Hermitian system. We offer a novel interpretation of the broken PT-symmetric regime as a non-ordered, non-probabilistic subalgebra of a larger Hermitian, fully quantum system. Additionally, our work clarifies the structural importance of positivity in standard quantum mechanics.