The Iterative Closest Point (ICP) algorithm is to align for the two point sets, which is widely used in map building of an uncertain environment. However, the original ICP algorithm is easily affected by noise and discrete points, making the error of alignment very large. At the same time, in a row scanning by the Laser Range Finder (LRF), the more data points accumulate, the larger the errors of alignment become, which leads to an unpreferable map, and the process would be time consuming. This paper proposes a map building of an uncertain environment based on an enhanced ICP (E-ICP) algorithm on the cloud, called E-ICP on the cloud, and presented a way to reduce duplicate reference point set. Thus, one can significantly reduce the computational burden, improve the accuracy of alignment, and get a more accurate environmental map.