We have isolated and characterized a xylanolytic actinomycete strain (RM1) from the extremely alkaline bauxite residue obtained from National Aluminum Company Ltd., Damanjodi, India. The phenotypic features and complete sequence of 16S rRNA revealed that this strain belong the genus Kocuria and showed 98% sequence similarity with Kocuria aegyptia. The RM1 strain was able to grow at pH 10.5 in buffered and unbuffered media and utilize 40 different carbon substrates. The RM1 strain under optimal conditions produced extracellular xylanase at 311 U/ml. The xylanase produced by RM1 showed a wide range of temperature (30–85°C) and pH (4.5–9) tolerance by retaining 90% of its activity. This is the first report of isolation of actinomycetes, Kocuria sp., which produces high amount of xylanase, from bauxite residue and offers a new source of xylanase-producing strains.