An exact spherically symmetric black hole solution of a recently proposed noncommutative gravity theory based on star products and twists is constructed. This is the first nontrivial exact solution of that theory. The resulting noncommutative black hole quite naturally exhibits holographic behavior; outside the horizon it has a fuzzy shell-like structure, inside the horizon it has a noncommutative de Sitter geometry. The star product and twist contain Killing vectors and act non-trivially on tensors except the metric, which is central in the algebra. The method used can be applied whenever there are enough spacetime symmetries. This includes noncommutati