We present a model of holographic dark energy in which the Infrared cutoff is determined by both the Ricci and the Gauss-Bonnet invariants. Such a construction has the significant advantage that the Infrared cutoff, and consequently the holographic dark energy density, does not depend on the future or the past evolution of the universe, but only on its current features, and moreover it is determined by invariants, whose role is fundamental in gravitational theories. We extract analytical solutions for the behavior of the dark energy density and equation-of-state parameters as functions of the redshift. These reveal the usual thermal history of the universe, with the sequence of radiation, matter and dark energy epochs, resulting in the future to a complete dark energy domination. The corresponding dark energy equation-of-state parameter can lie in the quintessence or phantom regime, or experience the phantom-divide crossing during the cosmological evolution, and its asymptotic value can be quintessence-like, phantom-like, or be exactly equal to the cosmological-constant value. Finally, we extract the constraints on the model parameters that arise from Big Bang Nucleosynthesis.