Summary: Cementitious structures exhibit high compression strength but suffer from inherent brittleness. Conversely, nature creates structures using mostly brittle phases that overcome the strength-toughness trade-off, mainly through internalized packaging of brittle phases with soft organic binders. Here, we develop complex architectures of cementitious materials using an inverse replica approach where a soft polymer phase emerges as an external conformal coating. Architected polymer templates are printed, cement pastes are molded into these templates, and cementitious structures with thin polymer surface coating are achieved after the solubilization of sacrificial templates. These polymer-coated architected cementitious structures display unusual mechanical behavior with considerably higher toughness compared to conventional non-porous structures. They resist catastrophic failure through delayed damage propagation. Most interestingly, the architected structures show significant deformation recovery after releasing quasi-static loading, atypical in conventional cementitious structures. This approach allows a simple strategy to build more deformation resilient cementitious structures than their traditional counterparts.