We study first-order electroweak phase transitions in the real-singlet-extended Standard Model, for which nonzero mixing between the Higgs field and the singlet can efficiently strengthen the transitions. We perform large-scale parameter-space scans of the model using two-loop effective potential at next-to-next-to-leading order in the high-temperature expansion, greatly improving description of phase transition thermodynamics over existing one-loop studies. We find that (1) two-loop corrections to the effective potential lead to narrower regions of strong first-order transitions and significantly smaller critical temperatures, (2) transitions involving a discontinuity in the singlet expectation value are significantly stronger at two-loop order, and (3) high-temperature expansion is accurate for a wide range of parameter space that allows strong transitions, although it is less reliable for the very strongest transitions. These findings suggest revisiting past studies that connect the possibility of a first-order electroweak phase transition with future collider phenomenology.