Energy storage units (ESUs) enable several attractive features of modern smart grids such as enhanced grid resilience, effective demand response, and reduced bills. However, uncoordinated charging of ESUs stresses the power system and can lead to a blackout. On the other hand, existing charging coordination mechanisms suffer from several limitations. First, the need for a central charging coordinator (CC) presents a single point of failure that jeopardizes the effectiveness of the charging coordination. Second, a transparent charging coordination mechanism does not exist where users are not aware whether the CC is honest or not in coordination charging requests among them in a fair way. Third, existing mechanisms overlook the privacy concerns of the involved customers. To address these limitations, in this paper, we leverage the blockchain and smart contracts to build a decentralized charging coordination mechanism without the need for a centralized charging coordinator. First ESUs should use tokens for anonymously authenticate themselves to the blockchain. Then each ESU sends a charging request that contains its State-of-Charge (SoC), Time-to-complete-charge (TCC) and amount of required charging to the smart contract address on the blockchain. The smart contract will then run the charging coordination mechanism in a self-executed manner such that ESUs with the highest priorities are charged in the present time slot while charging requests of lower priority ESUs are deferred to future time slots. In this way, each ESU can make sure that charging schedules are computed correctly. Finally, we have implemented the proposed mechanism on the Ethereum test-bed blockchain, and our analysis shows that execution cost can be acceptable in terms of gas consumption while enabling decentralized charging coordination with increased transparency, reliability, and privacy preserving.