The compostability of water-based paint sludge originating from the automotive industry was investigated. Six reactors were operated. Wastewater treatment sludge from the same industry was used as additional substrate, and corncob was used as a bulking agent. The level of paint sludge within the compost mixtures varied between 55 and 85%. All reactors yielded a temperature increase up to thermophilic phase levels (> 40 °C) for a minimum of 5 days, and organic matter and C/N losses were observed. BTEX concentrations decreased during composting. Nickel and tin levels in the final product exceeded the legal compost limits. The calorific value of the compost mixtures increased from 9532 to 18774 kJ/kg at the end of the composting process. It was seen that the process applied in this study can be utilized as a biodrying step before the usage of paint sludge at cement kilns as additional fuel.