The conventional micromechanical approaches today are still not able to properly predict the ductile-to-brittle transition (DBT) of steels because of their inability to consider the co-operating ductile fracture and cleavage mechanisms in the transition region, and simultaneously to incorporate the inherent complexity of microstructures. In this study, a complete methodology with coupled cellular automata finite element method (CAFE) and multi-barrier microcrack propagation models is presented to advance the prediction of DBT. The methodology contains three key elements: (i) a multiscale CAFE modelling approach to realize the competition between ductile damage and cleavage fracture and embrace the probabilistic nature of microstructures, (ii) a continuum approach to estimate the effective surface energy for a microcrack to penetrate over particle/matrix interface, and (iii) a method to calculate the effective surface energy for the microcrack to propagate across grain boundaries. The prediction of DBT therefore needs only (1) the stress-strain curves tested at different temperatures, (2) the activation energy for DBT, (3) the ratio between the size of cleavage facets and cleavage-initiating defects, and (4) key statistical distributions of the given microstructures. The proposed methodology can accurately reproduce the experimental DBT curve of a low carbon ultrahigh-strength steel.