Aluminum-ion batteries (AIBs) are attracting increasing attention as a potential energy storage system owing to the abundance of Al sources and high charge density of Al. However, suitable cathode materials to further advance high-performing AIBs are unavailable. Therefore, we demonstrated the compatibility of elemental metal nanoparticles (NPs) as cathode materials for AIBs. Three types of metal NPs (Co@C, Fe@C, CoFe@C) were formed by in-situ growing Prussian blue analogs (PBAs, Co[Co(CN)], Fe[Fe(CN)] and Co[Fe(CN)]) on a natural loofa (L) by a room-temperature wet chemical method in aqueous bath, followed by a carbonization process. The employed L effectively formed graphite C-encapsulated metal NPs after heat treatment. The discharge capacity of CoFe@C was superior (372 mAh g) than others (103 mAh g for Co@C and 75 mAh g for Fe@C). The novel design results in CoFe@C with an outstanding long-term charge/discharge cycling performance (over 1,000 cycles) with a Coulombic efficiency of 94.1%. Ex-situ X-ray diffraction study indicates these metal NP capacities are achieved through a solid-state diffusion-limited Al storage process. This novel design for cathode materials is highly significant for the further development of advanced AIBs in the future.