Extended dynamical mean-field theory (EDMFT) is insufficient to describe nonlocal effects in strongly correlated systems, since corrections to the mean-field solution are generally large. We present an efficient scheme for the construction of diagrammatic extensions of EDMFT that avoids the usual double-counting problem by using an exact change of variables (the Dual Boson formalism) to distinguish the correlations included in the dynamical mean-field solution and those beyond. With a computational efficiency comparable to the EDMFT + GW approach, our scheme significantly improves on the charge order transition phase boundary in the extended Hubbard model.