In this work we introduce the Dual Boson Diagrammatic Monte Carlo technique for strongly interacting electronic systems. This method combines the strength of dynamical mean-filed theory for non-perturbative description of local correlations with the systematic account of non-local corrections in the Dual Boson theory by the diagrammatic Monte Carlo approach. It allows us to get a numerically exact solution of the dual boson theory at the two-particle local vertex level for the extended Hubbard model. We show that it can be efficiently applied to description of single particle observables in a wide range of interaction strengths. We compare our exact results for the self-energy with the ladder Dual Boson approach and determine a physical regime, where description of collective electronic effects requires more accurate consideration beyond the ladder approximation. Additionally, we find that the order-by-order analysis of the perturbative diagrammatic series for the single-particle Greens function allows to estimate the transition point to the charge density wave phase.