The parallel-tempering Monte Carlo procedure is used to characterize the (CO2)(n), 17 = 6, 8, 13, and 19, clusters. The heat capacity curves of the n = 13 and 19 clusters are found to have pronounced peaks that can be associated with cluster melting. In addition, there is evidence of a low temperature "solid <----> solid" transition in the case Of (CO2)(19). The low-energy minima and rearrangement pathways are determined and used to examine the complexity of the potential energy surfaces of the clusters.