In this work, the rheological behavior of three crude oils, with low, middle and high wax content, in the absence/presence of polymeric and aromatic flow improvers was investigated. The rheological data cover the temperature range of 0 to 60 °C to include the wax appearance temperature (WAT). The results indicated that EVA copolymer has remarkable performance in change of flow behavior from non-Newtonian to Newtonian even at temperatures below WAT. Moreover, the addition of small quantities of asphaltene solvents such as toluene can improve viscosity of crude oil with high wax content. In addition to experimental and analytical modeling investigations, this work attempted to model measured shear stress and viscosity of waxy crude oils using tree-based machine learning methods and consider wax content and additives concentration as input parameters of models. Amongst all implemented techniques, Extra Trees model performed as a potential predictor in waxy oils rheology studies.