Tomographic reconstruction of cardiovascular structures from rotational angiograms acquired with interventional C-arm devices is challenging due to cardiac motion. Gating strategies are widely used to reduce data inconsistency but come at the cost of angular undersampling. We employ a spatio-temporally regularized 4-D reconstruction model, which is solved using a proximal algorithm, to handle the substantial undersampling associated with a strict gating setup. In a numerical phantom study based on the CAVAREV framework, similarity to the ground truth is improved from 82.3% to 87.6%by this approach compared to a state-of-the-art motion compensation algorithm, whereas previous regularized methods evaluated on this phantom achieved results below 80%. We also show first image results for a clinical patient data set.