With the continual increase in the high performance computing (HPC) market share, the need for a cheaper and widely available system rather than the expensive typical HPC systems increases. A promising alternative to HPC typical systems is the cloud computing environment which is characterised by being cheap, flexible, scalable and available. However, the cloud is based on virtualization which increases the latency to access the processing and network resources due to resource sharing. This makes the cloud an unpredictable environment to long run time programs such as HPC applications. Hence, modelling and understanding performance is essential for exploiting such environment. In this paper we propose a predictor for the execution time of the message passing interface (MPI) based applications on the cloud, as they are a major class of HPC applications. The predictor is based on an analytical performance model through considering the cloud resources as a queueing network, and the parallel applications as jobs contesting for the shared resources. The prediction based on the proposed model is measured on both a cluster of bare-metal servers and on a group of virtual machines. The overall accuracy of this prediction is 88% for 10 benchmarks, 5 from SPEC-MPI and 5 from NASA parallel benchmarks.