Multiscale heterogeneity and insufficient characterization data for the specific subsurface formation of interest render predictions of multi-phase fluid flow in geologic formations highly uncertain. Quantification of the propagation uncertainty from the geomodel to the fluid-flow response is typically done within a probabilistic framework. This task is computationally demanding due to, e.g., the slow convergence of Monte Carlo simulations (MCS), especially when computing the tails of a distribution that will be used for risk assessment and decision-making under uncertainty. The frozen streamlines method (FROST) accelerates probabilistic predictions of immiscible two-phase fluid flow problems; however, FROST still relies on MCS to compute the travel-time distribution, which is then used to perform the transport (phase saturation) computations. To alleviate this computational bottleneck, we replace MCS with a deterministic equation for the cumulative distribution function (CDF) of the travel time. The resulting CDF-FROST approach yields the CDF of the saturation field without resorting to sampling-based strategies. Our numerical experiments demonstrate the high accuracy of CDF-FROST in computing the CDFs of both saturation and travel time. For the same accuracy, it is about 5 and 10 times faster than FROST and MCS, respectively.