The deep penetration of electric vehicles (EVs) into the transportation section and the associated charging management has yielded a critical issue, namely, how to efficiently store the generated charging records. In this article, we investigate the cost-efficient charging-record storage scheme by exploiting blockchain (BC). Accounting for the operational cost due to the consensus process via the practical Byzantine fault tolerance (PBFT) protocol, we model the associated cost for storing the charging records via an ideal multiblockchain system and formulate a joint optimization of the storage selection (i.e., either storing the charging record locally or selecting one of the BCs for storing the charging record) and server-node allocation for each BC, with the objective of minimizing a systemwise cost. Despite the nature of the complicated mixed binary and integer programming problem, we exploit the decomposition structure and propose a layered algorithm (i.e., the bottom subproblem for determining the optimal storage selection and the top problem for finding the server-node allocation) to solve it. For the bottom subproblem, we exploit the nature of minimum weighted matching of the problem and propose a distributed auction-based algorithm for computing the optimal storage selection. With the optimal solution from the subproblem, we further propose an annealing-based algorithm to determine the server-node allocation for each BC. Numerical results are provided to validate the effectiveness of our proposed algorithms and the performance of our cost-efficient charging-record storage scheme via BC.