We study dyonic soliton and black hole solutions of the su(2) Einstein-Yang-Mills equations in asymptotically anti-de Sitter space. We prove the existence of non-trivial dyonic soliton and black hole solutions in a neighbourhood of the trivial solution. For these solutions the magnetic gauge field function has no zeros and we conjecture that at least some of these non-trivial solutions will be stable. The global existence proof uses local existence results and a nonlinear perturbation argument based on the (Banach space) implicit function theorem. © 2012 IOP Publishing Ltd.