We compute leading order corrections to black hole entropy due to small thermodynamic fluctuations, and show that they are always logarithmic in nature. When applied to asymptotically anti-de Sitter black holes, the predicted corrections are shown to match those from a holographic field theory on the boundary (including correct coefficients). The results are consistent with the AdS/CFT correspondence. We examine thermodynamic properties of the boundary theory.