The Kaluza-Klein excitations of gluons offer the exciting possibility of probing bulk Randall-Sundrum (RS) models. In these bulk models either a custodial symmetry or a deformation of the metric away from AdS is invoked in order to deal with electroweak precision tests. Addressing both these models, we suggest a new channel in which to study the production of KK-gluons ($g_{KK}$): one where it is produced in association with one or more hard jets. The cross-section for the $g_{KK}+$ jets channel is significant because of several contributing sub-processes. In particular, the 1-jet and the 2-jet associated processes are important because at these orders in QCD the $qg$ and the $gg$ initial states respectively come into play. We have performed a hadron-level simulation of the signal and present strategies to effectively extract the signal from what could potentially be a huge background. We present results for the kinematic reach of the LHC Run-II for different $g_{KK}$ masses in bulk-RS models.