Lithium decoration is an effective strategy for improving the hydrogen adsorption binding energy and the storage capacity in carbon nanostructures. Here, it is shown that Li-decorated double carbon vacancy graphene (DVG) can be used as an efficient hydrogen storage medium by means of Density Functional Theory (DFT) based calculations. The Li binding energy in DVG is 4.04 eV, which is much higher than that of pristine graphene. A maximum of four hydrogen molecules adsorb on Li decorated on one side of DVG and this leads to a gravimetric storage capacity of 3.89 wt% with an average adsorption binding energy of 0.23 eV/H-2. When Li is decorated on both sides of DVG, the gravimetric storage capacity reaches 7.26 wt% with a binding energy of 0.26 eV/H-2 which shows that desorption would take place at ambient conditions. Copyright (C) 2014, Hydrogen Energy Publications, LLC. Published by Elsevier Ltd. All rights reserved.