Distributed applications play an increasingly crucial role in business-critical enterprise operations. Understanding the performance of such applications is challenging yet essential due to their growing economic value. A particularly important problem is performance prediction: How will application-level performance vary in response to changes in workload? This paper presents a practical and accurate approach to predicting response times as a function of workload mix in complex modern distributed applications. We compare our approach against several alternatives, evaluating their ability to predict the performance of two large, real business-critical production systems and a testbed application subjected to extremely variable synthetic workload. Our results show that our method yields accurate response time predictions under a wide range of conditions, and that our models generalize well to previously-unseen regions of workload/performance space. 14 Pages