A continuum of new monopole and dyon solutions in the Einstein-Yang-Mills theory in asymptotically anti-de Sitter space are found. They are regular everywhere and specified by their mass and their non-Abelian electric and magnetic charges. A class of monopole solutions which have no node in non-Abelian magnetic fields is shown to be stable against spherically symmetric linear perturbations.