With the advances in virtualization technology, cloud has become the most powerful and promising platform for business, academia, public and government organizations. The cloud users do not require to maintain any IT infrastructure such as hardware, software and network resources in their premises. They can rent the services on demand from anywhere in the world just by paying for that service. In cloud computing, task allocation is a well-known problem. Many algorithms have been developed for the same. However, task allocation in a heterogeneous multi-cloud environment is much more challenging due to the dynamic nature of the cloud resources. In this paper, we present an algorithm, called uncertainty-based quality of service (QoS) Min–Min (UQMM) algorithm which considers QoS based on uncertainty parameters in heterogeneous multi-cloud environment. To the best of our knowledge, this is the first paper which deals with the task allocation problem with uncertainty-based QoS in a heterogeneous multi-cloud systems. We perform extensive simulations on the proposed algorithm using benchmark as well as synthetic datasets and measure performance in terms of various metrics. The results are compared with the popular cloud min–min scheduling, cloud min–max normalization and smoothing-based task scheduling algorithm to show the effectiveness of the proposed algorithm. Moreover, we evaluate the results using two statistical tests, namely t test and ANOVA.