Terrestrial laser scanning (TLS) has become a popular tool for acquiring source data points which can be used to construct digital elevation models (DEMs) for a wide number of applications. A TLS point cloud often has a very fine spatial resolution, which can represent well the spatial variation of a terrain surface. However, the uncertainty in DEMs created from this relatively new type of source data is not well understood, which forms the focus of this letter. TLS survey data representing four terrain surfaces of different characteristics were used to explore the effects of surface complexity and typical TLS data density (in terms of data point spacing) on DEM accuracy. The spatial variation in TLS data can be decomposed into parts corresponding to the signal of spatial variation (of terrain surfaces) and noise due to measurement error. We found a linear relation between the DEM error and the typical TLS data spacings considered (30-100 mm) which arises as a function of the interpolation error, and a constant contribution from the propagated data noise. This letter quantifies these components for each of the four surfaces considered and shows that, for the interpolation method considered here, higher density sampling would not be beneficial.