We present, perhaps for the first time, a stochastic search algorithm in quantitative photoacoustic tomography (QPAT) for a one-step recovery of the optical absorption map from time-resolved photoacoustic signals. Such a direct recovery is free of the numerical inaccuracies inherent in conventional two-step approaches that depend on an accurate estimation of the absorbed energy distribution. The absorption profile parameterized as a vector stochastic process is additively updated over time recursions so as to drive the measurement-prediction misfit to a zero-mean white noise. The derivative-free additive update is a welcome departure from the conventional gradient-based methods requiring evaluation of Jacobians at every recursion. The quantitative accuracy of the recovered absorption map from both numerical and experimental data is good with an overall error of less than 10%.