Nucleation and grain growth are important phenomena during static recrystallization of metallic materials and both processes have significant influences on the material properties. The Monte Carlo (MC) method has been widely used to simulate static recrystallization behavior during annealing of metallic materials. In this study, an MC model for static recrystallization of two-phase alloys is proposed by extending an existing MC model, through the introduction of the nucleation stage to account for the grain growth by both consuming deformed grains and competing with other recrystallized grains. The two-phase MC model is used to simulate the evolution of microstructure and texture during annealing of a TC11 (Ti-6.5Al-3.5Mo-1.5Zr-0.3Si) titanium alloy, accounting for initial grain morphology, phase compositions, crystallographic orientations, and relative values of strain stored energy determined by electron back-scattered diffraction. The results show that the model can reproduce satisfactorily the recrystallization and grain growth behavior in annealing. Compared with the β phase, the α phase depicts a lower recrystallization rate but a higher grain growth rate: the former difference can be mainly attributed to the lower strain stored energy in the α phase before annealing, whereas the latter suggests that the grain growth in the system is significantly influenced by the grain morphology, distribution of grains, and relative volume fractions of the two phases in the initial condition. Due to the influence of heterogeneous nucleation accounted for in the model, the simulated recrystallization rate deviates considerably from that described by the Johnson-Mehl-Avrami-Kolmogorov equation. The simulation also indicates that for both phases the textures strengthen with little changes in their basic features during annealing.