Background: Bacteria of the genus Arthrobacter are ubiquitous in soil environments and can be considered as true survivalists. Arthrobacter sp. strain Rue61a is an isolate from sewage sludge able to utilize quinaldine (2- methylquinoline) as sole carbon and energy source. The genome provides insight into the molecular basis of the versatility and robustness of this environmental Arthrobacter strain. Results: The genome of Arthrobacter sp. Rue61a consists of a single circular chromosome of 4,736,495 bp with an average G + C content of 62.32%, the circular 231,551-bp plasmid pARUE232, and the linear 112,992-bp plasmid pARUE113 that was already published. Plasmid pARUE232 is proposed to contribute to the resistance of Arthrobacter sp. Rue61a to arsenate and Pb2+, whereas the linear plasmid confers the ability to convert quinaldine to anthranilate. Remarkably, degradation of anthranilate exclusively proceeds via a CoA-thioester pathway. Apart from quinaldine utilization, strain Rue61a has a limited set of aromatic degradation pathways, enabling the utilization of 4-hydroxy-substituted aromatic carboxylic acids, which are characteristic products of lignin depolymerization, via ortho cleavage of protocatechuate. However, 4-hydroxyphenylacetate degradation likely proceeds via meta cleavage of homoprotocatechuate. The genome of strain Rue61a contains numerous genes associated with osmoprotection, and a high number of genes coding for transporters. It encodes a broad spectrum of enzymes for the uptake and utilization of various sugars and organic nitrogen compounds. A. aurescens TC-1 is the closest sequenced relative of strain Rue61a. Conclusions: The genome of Arthrobacter sp. Rue61a reflects the saprophytic lifestyle and nutritional versatility of the organism and a strong adaptive potential to environmental stress. The circular plasmid pARUE232 and the linear plasmid pARUE113 contribute to heavy metal resistance and to the ability to degrade quinaldine, respectively.