Neutrinos, the enigmatic weakly interacting particles, may hold the keys to some of the fascinating puzzles in particle physics and cosmology. On one hand, they demonstrate the quantum mechanical effect of flavor mixing -- on macroscopic distance scales -- and thereby violate a conservation law thought to be valid only two decades ago -- the conservation of lepton flavor. On the other hand, neutrino is the only known particle that may be a Majorana fermion, or identical to its antiparticle. Processes involving Majorana neutrinos could violate the lepton number conservation -- an empirical property of the Standard Model that, unlike other conservation laws, is not explained by a known symmetry principle. Neutrinoless Double Beta Decay (0nuDBD) is a rare nuclear process that is possible only if neutrinos are Majorana fermions. Observation of 0nuDBD would change our understanding of the nature of neutrinos, may provide a strong evidence for the role of neutrinos in generating matter-antimatter asymmetry in the early Universe, and set the scale for the absolute values of neutrino masses. CUORE, a cryogenic experiment constructed jointly by the US and Italy at Gran Sasso National Laboratories and set to begin operations next year, will be one of the most sensitive 0nuDBD experiments this decade. We will review the history of DBD searches, discuss the unique features of CUORE, and also outline what the next decade may bring to this exciting field.