Melamine belongs to the s-triazine family, and industrially used as raw product in many ways all over the world. Melamine has been reported for human harmful effects and detected from some crops, soil and water. To remove melamine from the polluted environment, the efficient melamine-mineralizing microorganisms have been needed. We newly isolated three melamine-degrading bacteria from the same upland soil sample using soil-charcoal perfusion method. These bacteria were classified as Arthrobacter sp. MCO, Arthrobacter sp. CSP and Microbacterium sp. ZEL by 16S rRNA genes sequencing analysis. Both Arthrobacter species completely degraded melamine within 2 days, and consumed melamine as a sole nitrogen source. Both strains also grew in cyanuric acid as sole nitrogen source, and released small quantities of ammonium ions. These strains are the first identified bacteria that can mineralize both melamine and cyanuric acid as sole initial nitrogen source in Arthrobacter sp. Although ammeline and ammelide intermediates were detected, these strains possess none of the known genes encoding melamine degrading enzymes. Since the Arthrobacter strains also degraded melamine in a high pH liquid medium, they present as potential bioremediation agents in melamine-polluted environments.