We synthesized a new type of carbon-polynanocrystalline graphite-by chemical vapor deposition on a nanoporous graphenic carbon as an epitaxial template. This carbon is composed of nanodomains being highly graphitic along c-axis and very graphenic along ab plane directions, where the nanodomains are randomly packed to form micron-sized particles, thus forming a polynanocrystalline structure. The polynanocrystalline graphite is very unique, structurally different from low-dimensional nanocrystalline carbon materials, e.g., fullerenes, carbon nanotubes, and graphene, nanoporous carbon, amorphous carbon and graphite, where it has a relatively low specific surface area of 91 m2/g as well as a low Archimedes density of 0.92 g/cm3. The structure is essentially hollow to a certain extent with randomly arranged nanosized graphite building blocks. This novel structure with disorder at nanometric scales but strict order at atomic scales enables substantially superior long-term cycling life for K-ion storage as an anode, where it exhibits 50% capacity retention over 240 cycles, whereas for graphite, it is only 6% retention over 140 cycles.