A method and apparatus for cleaning rubber deposits from surfaces such as airport runways and roadways is disclosed. The apparatus includes a large vehicle that has the capacity to be loaded so as to effectively add weight to the rubber cleaning tires of the vehicle. In addition, the vehicle has a water tank and sprinkler system so that the surface may be wetted down in front of the tires as the vehicle proceeds across the surface. The cleaning tires of the apparatus are aligned so that they are at a yaw angle to the direction of travel, and the cleaning tire assembly is attached to the underside of the trailer of the vehicle and positioned between a forward and rear water tank. In addition, this tire assembly is equipped with a means of loading the tires onto the contaminated surface. The method comprises driving such a vehicle at low speeds down the surface as the road is being wet in front of the cleaning tires. The effect of the angled tires is to create a scrubbing action that not only heats the rubber deposits by friction but also causes it to be removed from the surface. The rubber that does not stick to the cleaning tires is then removed from the surface by sweeping.