This paper examines the effect of non-uniform microstructures on the macroscopic fracture properties of idealized brick and mortar composites, which consist of rigid bricks bonded with elastic–plastic mortar that ruptures at finite strain. A simulation tool that harnesses the parallel processing power of graphics processing units (GPUs) was used to simulate fracture in virtual specimens, whose microstructures were generated by sampling a probability distribution of brick sizes. In the simulations, crack advance is a natural outcome of local ruptures in the cohesive zones bonding the bricks: the macroscopic initiation toughness for small-scale yielding is inferred by correlating the critical load needed to advance a pre-defined crack with an associated far-field energy release rate. Quantitative connections between the statistical parameters defining heterogeneous brick distributions and the statistics of initiation toughness are presented. The nature of crack tip damage and stresses ahead of the crack tip are illustrated as a function of brick size variability. The results offer quantitative insights that can be used to identify microstructural targets for process development, notably specific brick size distributions that still provide macroscopic toughening.