The air traffic is mainly divided into en-route flight segments, arrival and departure segments inside the terminal maneuvering area, and ground operations at the airport. To support utilizing available capacity more efficiently, in our contribution we focus on the prediction of arrival procedures, in particular, the time-to-fly from the turn onto the final approach course to the threshold. The predictions are then used to determine advice for the controller regarding time-to-lose or time-togain for optimizing the separation within a sequence of aircraft. Most prediction methods developed so far provide only a point estimate for the time-to-fly. Complementary, we see the need to further account for the uncertain nature of aircraft movement based on a probabilistic prediction approach. This becomes very important in cases where the air traffic system is operated at its limits to prevent safety-critical incidents, e.g., separation infringements due to very tight separation. Our approach is based on the Quantile Regression Forest technique that can provide a measure of uncertainty of the prediction not only in form of a prediction interval but also by generating a probability distribution over the dependent variable. While the data preparation, model training, and tuning steps are identical to classic Random Forest methods, in the prediction phase, Quantile Regression Forests provide a quantile function to express the uncertainty of the prediction. After developing the model, we further investigate the interpretation of the results and provide a way for deriving advice to the controller from it. With this contribution, there is now a tool available that allows a more sophisticated prediction of time-to-fly, depending on the specific needs of the use case and which helps to separate arriving aircraft more efficiently.