Despite significant recent advances in the regularity theory for obstacle problems with integro-differential operators, some fundamental questions remained open. On the one hand, there was a lack of understanding of parabolic problems with critical scaling, such as the obstacle problem for \partial_t+\sqrt{-\Delta}. No regularity result for free boundaries was known for parabolic problems with such scaling. On the other hand, optimal regularity estimates for solutions (to both parabolic and elliptic problems) relied strongly on monotonicity formulas and, therefore, were known only in some specific cases. In this paper, we present a novel and unified approach to answer these open questions and, at the same time, to treat very general operators, recovering as particular cases most previously known regularity results on nonlocal obstacle problems.