A method is presented for modeling the behavior of a given class of applications executing in real workloads on a particular machine. The methodology is illustrated by modeling the execution of computationally bound, parallel applications running in real workloads on an Alliant FX/80. The model is constructed from real measured data obtained during normal machine operation and can capture intricate multiple job interactions, such as contention for shared resources. The model is a finite-state, discrete-time Markov model with rewards and costs associated with each state. The model can predict the distribution of completion times in real workloads for a given application. The predictions are useful in gauging how quickly an application will execute, or in predicting the effects of a system change on performance. The model is validated with three separate sets of empirical data. In one validation, the model successfully predicts the effects of operating the machine with one less processor.