Small particles have a lower melting point than bulk material(1). The physical cause lies in the fact that small particles have a higher proportion of surface atoms than larger particles-surface atoms have fewer nearest neighbours and are thus more weakly bound and less constrained in their thermal motion(2,3) than atoms in the body of a material. The reduction in the melting point has been studied extensively for small particles or clusters on supporting surfaces. One typically observes a linear reduction of the melting point as a function of the inverse cluster radius(2,4,5). Recently, the melting point of a very small cluster, containing exactly 139 atoms, has been measured in a vacuum using a technique in which the cluster acts as its own nanometre-scale calorimeter(6,7). Here we use the same technique to study ionized sodium clusters containing 70 to 200 atoms. The melting points of these dusters are on average 33% (120 K) lower than the bulk material; furthermore, we observe surprisingly large variations in the melting point (of +/-30 K) with changing cluster size, rather than any gradual trend. These variations cannot yet be fully explained theoretically.