Using high-contrast imaging with the SPHERE instrument at the Very Large Telescope (VLT), we report the first images of a cold brown dwarf companion to the exoplanet host star HD 4113A. The brown dwarf HD 4113C is part of a complex dynamical system consisting of a giant planet, a stellar host, and a known wide M-dwarf companion. Its separation of 535 ± 3 mas and H-band contrast of 13.35 ± 0.10 mag correspond to a projected separation of 22 AU and an isochronal mass estimate of 36 ± 5 MJ based on COND models. The companion shows strong methane absorption, and through fitting an atmosphere model, we estimate a surface gravity of logg = 5 and an effective temperature of ~500–600 K. A comparison of its spectrum with observed T dwarfs indicates a late-T spectral type, with a T9 object providing the best match. By combining the observed astrometry from the imaging data with 27 years of radial velocities, we use orbital fitting to constrain its orbital and physical parameters, as well as update those of the planet HD 4113A b, discovered by previous radial velocity measurements. The data suggest a dynamical mass of 66−4+5 $66^{+5}_{-4}$ 66−4+5 MJ and moderate eccentricity of 0.44−0.07+0.08 $0.44^{+0.08}_{-0.07}$ 0.44−0.07+0.08 for the brown dwarf. This mass estimate appears to contradict the isochronal estimate and that of objects with similar temperatures, which may be caused by the newly detected object being an unresolved binary brown dwarf system or the presence of an additional object in the system. Through dynamical simulations, we show that the planet may undergo strong Lidov-Kozai cycles, raising the possibility that it formed on a quasi-circular orbit and gained its currently observed high eccentricity (e ~ 0.9) through interactions with the brown dwarf. Follow-up observations combining radial velocities, direct imaging, and Gaia astrometry will be crucial to precisely constrain the dynamical mass of the brown dwarf and allow for an in-depth comparison with evolutionary and atmosphere models.