The ${alpha}$-galactosidase-coding gene agaAJB13 was cloned from Sphingomonas sp. JB13 showing 16S rDNA (1,343 bp) identities of ${leq}97.2%$ with other identified Sphingomonas strains. agaAJB13 (2,217 bp; 64.9% GC content) encodes a 738-residue polypeptide (AgaAJB13) with a calculated mass of 82.3 kDa. AgaAJB13 showed the highest identity of 61.4% with the putative glycosyl hydrolase family 36 ${alpha}$-galactosidase from Granulicella mallensis MP5ACTX8 (EFI56085). AgaAJB13 also showed <37% identities with reported protease-resistant or Sphingomonas ${alpha}$-galactosidases. A sequence analysis revealed different catalytic motifs between reported Sphingomonas ${alpha}$-galactosidases (KXD and RXXXD) and AgaAJB13 (KWD and SDXXDXXXR). Recombinant AgaAJB13 (rAgaAJB13) was expressed in Escherichia coli BL21 (DE3). The purified rAgaAJB13 was characterized using p-nitrophenyl-${alpha}$-D-galactopyranoside as the substrate and showed an apparent optimum at pH 5.0 and $60^{circ}C$ and strong resistance to trypsin and proteinase K digestion. Compared with reported proteaseresistant ${alpha}$-galactosidases showing thermolability at $50^{circ}C$ or $60^{circ}C$ and specific activities of <71 U/mg with or without protease treatments, rAgaAJB13 exhibited a better thermal stability (half-life of >60 min at $60^{circ}C$) and higher specific activities (225.0-256.5 U/mg). These sequence and enzymatic properties suggest AgaAJB13 is the first identified and characterized Sphingomonas ${alpha}$-galactosidase, and shows novel protease resistance with a potential value for basic research and industrial applications.