Magnetic reconnection can power bright and rapid flares originating from the inner magnetosphere of accreting black holes. We conduct extremely high resolution general-relativistic magnetohydrodynamics and general relativistic particle in cell simulations, capturing plasmoid-mediated reconnection at black hole event horizons for the first time. We will show that an equatorial, plasmoid-unstable current sheet forms in a transient, non-axisymmetric, low-density magnetosphere within the inner ten Schwarzschild radii. Magnetic flux is expelled from the event horizon through reconnection at a universal plasmoid-mediated rate in this current sheet. The current sheet is fed by the highly-magnetized plasma in the magnetosphere, heating the plasma trapped in flux tubes to temperatures proportional to the magnetosphere's magnetization. The reconnection produces sufficiently energetic plasma to explain flares originating from nearby the horizon of accreting black holes, such as the TeV emission observed from M87. The drop in mass accretion rate during the flare, and the resulting low-density magnetosphere make it easier for very high energy photons produced by reconnection-accelerated particles to escape. The plasmoid-mediated reconnection rate directly determines the timescales and properties of the flare. Large flux tubes are expelled from the reconnection exhaust into the accretion disk and can orbit for an orbital period as low-density hot spots, in accordance with Sgr A* observations by the GRAVITY interferometer.