Realizing a strong interaction between individual optical photons is an important objective of research in quantum science and technology. Since photons do not interact directly, this goal requires, e.g., an optical medium in which the light experiences a phase shift that depends nonlinearly on the photon number. Once the additional phase shift for two photons reaches pi, such an ultra-strong nonlinearity could even enable the direct implementation of high-fidelity quantum logic operations. However, the nonlinear response of standard optical media is many orders of magnitude too weak for this task. Here, we demonstrate the realization of an optical fiber-based nonlinearity that leads to an additional two-photon phase shift close to the ideal value of pi. Our scheme employs a whispering-gallery-mode resonator, interfaced by an optical nanofiber, where the presence of a single rubidium atom in the resonator results in a strongly nonlinear response. We experimentally show that this results in entanglement of initially independent incident photons. The demonstration of this ultra-strong nonlinearity in a fiber-integrated system is a decisive step towards scalable quantum logics with optical photons.