Using extensive, unbiased searches based on density-functional theory, we explore the structural evolution of Cun clusters over the size range n=8-20. For n=8-16, the optimal structures are plateletlike, consisting of two layers, with the atoms in each layer forming a trigonal bonding network similar to that found in smaller, planar clusters (n≤6). For n=17 and beyond, there is a transition to compact structures containing an icosahedral 13-atom core. The calculated ground-state structures are significantly different from those predicted earlier in studies based on empirical and semiempirical potentials. The evolution of the structure and shape of the preferred configuration of Cun, n≤20, is shown to be nearly identical to that found for Na clusters, indicating a shell-model-type behavior in this size range.