For the first time, by atomic force microscopy (AFM) methods, micro- and nanofragments of micronized powder elastomeric modifier (PEM) formed at the short-term (3 min at 160 °C) interaction of PEM with hot bitumen have been demonstrated. It is the technology of high-temperature shear-induced grinding of a worn-out tire’s crumb rubber or its co-grinding with styrene–butadiene–styrene (SBS) block copolymer which provides the creation of the PEM structure inclined to rapid degradation in hot bitumen. The formation just after the preparation process of a new structure of a modified binder, more resistant to external effects, is supported by the data of rheological tests. Performance tests for a modified binder using Superpave standard adopted by the road industry for bituminous binders showed an extended temperature range, resistance to rutting, and low-temperature and fatigue cracking. The better resistance to low-temperature and fatigue cracking is certainly related to energy absorption and crack growth stopping in the presence of micron and submicron resilient PEM fragments in accordance with the mechanism of increasing impact toughness in plastics.