Robot localization plays an important role in the field of robot navigation. One of the most commonly used localization algorithms is Monte Carlo Localization algorithm (MCL). Unfortunately, the traditional MCL is not reliable all the time in both pose tracking and global localization. Many modified MCL algorithms have been proposed to improve the efficiency and performance, such as improved Monte Carlo Localization with robust orientation estimation algorithm (IMCLROE) proposed by the authors. However, the IMCLROE requires a lot of storage space and intensive computation, especially in a highly complicated environment. In recent years, cloud computing has been widely used because of ubiquitous network. As an attempt to solve the above problems based on cloud computing, we propose a cloud-based improved Monte Carlo Localization algorithm with robust orientation estimation with a distributed orientation estimation technique in calculating important factor of each particle. With the use of cloud computing, real-time paradox between accuracy and efficiency in a high-resolution grid map can be addressed. Experimental results confirm that the proposed cloud-based architecture can efficiently establish a map database and reduce the computational load for robot localization.