Provided are a computer program product, system, and method for maintaining data structures in a virtual memory comprised of a plurality of heterogeneous memory devices. Access counts are maintained for a plurality of data structures stored in a first level memory device. A determination is made of data structures in the first level memory device having lowest access counts. The determined data structures are deleted from the first level memory device and retaining copies of the data structures in a second level memory device, wherein the first level memory device has lower latency than the second level memory device.