The search for a universal memory storage device that combines rapid read and write speeds, high storage density and non-volatility is driving the exploration of new materials in nanostructured form. Phase-change materials, which can be reversibly switched between amorphous and crystalline states, are promising in this respect, but top-down processing of these materials into nanostructures often damages their useful properties. Self-assembled nanowire-based phase-change material memory devices offer an attractive solution owing to their sub-lithographic sizes and unique geometry, coupled with the facile etch-free processes with which they can be fabricated. Here, we explore the effects of nanoscaling on the memory-storage capability of self-assembled Ge2Sb2Te5 nanowires, an important phase-change material. Our measurements of write-current amplitude, switching speed, endurance and data retention time in these devices show that such nanowires are promising building blocks for non-volatile scalable memory and may represent the ultimate size limit in exploring current-induced phase transition in nanoscale systems.