GJ 367 is a bright (V ≈ 10.2) M1 V star that has been recently found to host a transiting ultra-short period sub-Earth on a 7.7 hr orbit. With the aim of improving the planetary mass and radius and unveiling the inner architecture of the system, we performed an intensive radial velocity follow-up campaign with the HARPS spectrograph-collecting 371 high-precision measurements over a baseline of nearly 3 yr-and combined our Doppler measurements with new TESS observations from sectors 35 and 36. We found that GJ 367 b has a mass of M b = 0.633 ± 0.050 M ⊕ and a radius of R b = 0.699 ± 0.024 R ⊕, corresponding to precisions of 8% and 3.4%, respectively. This implies a planetary bulk density of ρ b = 10.2 ± 1.3 g cm-3, i.e., 85% higher than Earth's density. We revealed the presence of two additional non-transiting low-mass companions with orbital periods of ~11.5 and 34 days and minimum masses of ${M}_{{\rm{c}}}\sin {i}_{{\rm{c}}}$ = 4.13 ± 0.36 M ⊕ and ${M}_{{\rm{d}}}\sin {i}_{{\rm{d}}}$ = 6.03 ± 0.49 M ⊕, respectively, which lie close to the 3:1 mean motion commensurability. GJ 367 b joins the small class of high-density planets, namely the class of super-Mercuries, being the densest ultra-short period small planet known to date. Thanks to our precise mass and radius estimates, we explored the potential internal composition and structure of GJ 367 b, and found that it is expected to have an iron core with a mass fraction of ${0.91}_{-0.23}^{+0.07}$ . How this iron core is formed and how such a high density is reached is still not clear, and we discuss the possible pathways of formation of such a small ultra-dense planet. *Based on observations made with the ESO-3.6 m telescope at La Silla Observatory under programs 1102.C-0923 and 106.21TJ.001.