We investigate compact minimal surfaces in the Einstein-Maxwell theory with both electric and magnetic charges and a negative cosmological constant. A two-sided, embedded and strictly stable minimal surface that maximizes the magnetically charged Hawking mass naturally corresponds to the event horizon of a black hole. Our main theorem shows that the geometry near such a surface is rigid: a neighborhood is isometric to the dyonic Reissner-Nordstrom-Anti-de Sitter space, the canonical model of a charged black hole in Anti-de Sitter spacetime. In addition, we provide an area estimate for the surface that depends only on its topology and the relevant physical parameters.