An optimization-driven approach is presented to create a “double-tough” ceramic. The material features two main toughening mechanisms – crack deflection in a brick-and-mortar microstructure, and transformation toughening in the mortar – and it is engineered to achieve high strength and fracture toughness levels simultaneously. The material design involves high-strength alumina bricks interconnected via a ceria-stabilized zirconia mortar. Given that the design of the optimal material, featuring multiscale toughening mechanisms, typically requires a laborious trial-and-error approach, a Bayesian optimization framework is proposed to streamline and accelerate the experimental campaign. A Gaussian process is used to emulate the material’s mechanical response, and a cost-aware batch Bayesian optimization is implemented to efficiently identify optimal design process parameters, accounting for the cost of experimentally varying them. This approach expedites the optimization of the material’s mechanical properties. As a result, a bio-inspired all-ceramic composite is developed, exhibiting an exceptional balance between bending strength (704MPa) and fracture toughness (13.6MPam^0.5), along with a stress intensity factor at crack initiation of 6.7MPam^0.5. The material exhibits significantly higher strength than both nacre-like ceramic composites and transformation-toughened zirconia at comparable toughness levels.