Disorder-induced magnetoresistance (MR) effect is quadratic at low perpendicular magnetic fields and linear at high fields. This effect is technologically appealing, especially in the two-dimensional (2D) materials such as graphene, since it offers potential applications in magnetic sensors with nanoscale spatial resolution. However, it is a great challenge to realize a graphene magnetic sensor based on this effect because of the difficulty in controlling the spatial distribution of disorder and enhancing the MR sensitivity in the single-layer regime. Here, we report a room-temperature colossal MR of up to 5,000% at 9 T in terraced single-layer graphene. By laminating single-layer graphene on a terraced substrate, such as TiO2 terminated SrTiO3, we demonstrate a universal one order of magnitude enhancement in the MR compared to conventional single-layer graphene devices. Strikingly, a colossal MR of >1,000% was also achieved in the terraced graphene even at a high carrier density of ~1012 cm-2. Systematic studies of the MR of single-layer graphene on various oxide- and non-oxide-based terraced surfaces demonstrate that the terraced structure is the dominant factor driving the MR enhancement. Our results open a new route for tailoring the physical property of 2D materials by engineering the strain through a terraced substrate.