The ability to predict system performance is key to enabling better system optimization and planning. Given recent advances in Machine learning (ML), one might ask whether ML is a natural fit for this task. We study whether and how ML can be used to predict performance. Our findings reveal that the performance variability stemming from optimization or randomization techniques in many applications makes performance prediction inherently difficult, i.e. in such cases, no ML technique can predict performance with high enough accuracy. We show how eliminating the discovered sources of variability greatly improves prediction accuracy. Since it is difficult to eliminate all possible sources of system performance variability, we further discuss how ML models can be extended to cope with them by learning a distribution as opposed to point estimates.