Bitumen is a widely used material employed as a binder in pavement engineering and as a surface sealant in construction. Its surface microstructure and microscale properties have been shown to be temperature-dependent, with effects manifesting themselves on surface composition and texture, including the formation of the visually striking catana "bee"-like structures. Despite the importance of a good performance of bitumen in sub-zero environments (< 0 °C), the behavior of bitumen surface texture and composition at cold temperatures, affecting cracking, degradation, and road icing, has received practically no attention. In particular, such knowledge is relevant to world regions experiencing long periods of sub-zero temperatures during the year. Employing advanced atomic force microscopy combined with infrared spectroscopy (AFM-IR) and an environmental chamber, we demonstrate the ability to characterize surface structure and composition with nanoscale precision for a broad range of temperatures. We show that cooling bitumen to sub-zero temperatures can have several interesting effects on its surface micro-texture, nano-texture, and composition, especially on its three surface domains, catana, peri, and para. We found that the para domain coarsens and extends to form an interfacial transition domain (characterized by increasing surface roughness with peri domain composition) between the para and peri domains. We show that the catana and peri domains have a similar composition, but have different mechanical and chemical properties compared to the para domain. The essential findings of this work improve our understanding of the behavior of bitumen in sub-zero environments, aiding us in our quest towards attaining better road and sealant performance. This article is protected by copyright. All rights reserved.