<jats:p>Two novel cold-tolerant, Gram-stain-positive, motile, facultatively anaerobic bacterial strains, LI2<jats:sup>T</jats:sup> and LI3<jats:sup>T</jats:sup>, were isolated from moss-covered soil from Livingston Island, Antarctica, near the Bulgarian station St Kliment Ohridski. A rod–coccus cycle was observed for both strains. 16S rRNA gene sequence analysis revealed an affiliation to the genus <jats:italic>Arthrobacter</jats:italic>, with the highest similarity to <jats:italic>Arthrobacter stackebrandtii</jats:italic> and <jats:italic>Arthrobacter psychrochitiniphilus</jats:italic> for strain LI2<jats:sup>T</jats:sup> (97.8 and 97.7 % similarity to the respective type strains) and to <jats:italic>Arthrobacter kerguelensis</jats:italic> and <jats:italic>Arthrobacter psychrophenolicus</jats:italic> for strain LI3<jats:sup>T</jats:sup> (97.4 and 97.3 % similarity to the respective type strains). The growth temperature range was −6 to 28 °C for LI2<jats:sup>T</jats:sup> and −6 to 24 °C for LI3<jats:sup>T</jats:sup>, with an optimum at 16 °C for both strains. Growth occurred at 0–10 % (w/v) NaCl, with optimum growth at 0–1 % (w/v) for LI2<jats:sup>T</jats:sup> and 0.5–3 % (w/v) for LI3<jats:sup>T</jats:sup>. The pH range for growth was pH 4–9.5 with an optimum of pH 8 for LI2<jats:sup>T</jats:sup> and pH 6.5 for LI3<jats:sup>T</jats:sup>. The predominant fatty acids were anteiso-C<jats:sub>15 : 0</jats:sub>, C<jats:sub>18 : 0</jats:sub> and anteiso-C<jats:sub>17 : 0</jats:sub> for LI2<jats:sup>T</jats:sup> and anteiso-C<jats:sub>15 : 0</jats:sub> and C<jats:sub>18 : 0</jats:sub> for LI3<jats:sup>T</jats:sup>. Physiological and biochemical tests clearly differentiated strain LI2<jats:sup>T</jats:sup> from <jats:italic>A. stackebrandtii</jats:italic> and <jats:italic>A. psychrochitiniphilus</jats:italic> and strain LI3<jats:sup>T</jats:sup> from <jats:italic>A. kerguelensis</jats:italic> and <jats:italic>A. psychrophenolicus</jats:italic>. Therefore, two novel species within the genus <jats:italic>Arthrobacter</jats:italic> are proposed: <jats:italic>Arthrobacter livingstonensis</jats:italic> sp. nov. (type strain LI2<jats:sup>T</jats:sup>  = DSM 22825<jats:sup>T</jats:sup>  = NCCB 100314<jats:sup>T</jats:sup>) and <jats:italic>Arthrobacter cryotolerans</jats:italic> sp. nov. (type strain LI3<jats:sup>T</jats:sup>  = DSM 22826<jats:sup>T</jats:sup>  = NCCB 100315<jats:sup>T</jats:sup>).</jats:p>