To maximize its own profit, cloud service brokerage (CSB) aims to distribute tenant demands to reserved servers such that the total reservation cost is minimized with the tenants' service level agreement (SLA) being satisfied. The demand allocation problem for CSB is non-trivial to solve due to uncertainty of tenants' behavior. To avoid possible violations among demands, existing schemes allocate additional padding resources on the predicted demands, which leads to under-utilization of reserved resources. Accordingly, we propose a Probabilistic Demand Allocation (PDA) system to address the demand allocation problem for CSB. In PDA, we not only predict tenants' demands based on their historical records, but also estimate the probability distribution of prediction errors. As over- and under-estimation are equally likely to happen with our prediction method, when allocating demands to a single server, their errors are possibly offset. Hence, it is unnecessary to allocate additional resource to each demand for violation prevention. Given the predication results, we formulate the demand allocation problem by probabilistic optimization, of which the objective is to minimize the overall cost from reserved servers while satisfying tenants' SLA with high probability. Both simulation and real-world experimental results demonstrate the superiority of PDA in reducing servers' reservation cost.