An almost complete and partially articulated skeleton of an Early Pleistocene baleen whale is here described. The fossil, measuring 11 m in length, was discovered in the Calcarenite di Gravina Formation at Lama Lamasinata site (Bari, southern Italy) in 1968. The bifurcated first rib combined with other characters supports the identification of the fossil whale as a possible undescribed species of Balaenoptera (Mysticeti, Balaenopteridae), close to or nested in the B. borealis–B. edeni–B. ricei clade. However, the limited number of preserved diagnostic characters suggests a prudent assignment of the Bari whale to Balaenoptera sp. The associated molluscs suggest a mid-shelf setting deposition near to the boundary between infralittoral and circalittoral environments, probably 40–60 m deep. An associated Carcharodon carcharias tooth (the first case of a possible trophic interaction between white shark and cetaceans in the Pleistocene) and shark bite marks on a rib support the hypothesis that an early scavenger action prevented the rising of the whale carcass because of the removal of abdominal tissues and the consequent reduction of the decomposition gas accumulation. The occurrence of chemosymbiotic bivalves near the skeleton could testify the development of the sulphophilic stage during decay. Overall, the Bari whale skeleton and its associated fossil fauna represent the first well-documented case of Pleistocene whale fall community. The Bari specimen sheds new light on the diversity and disparity of the mysticete fauna in the Mediterranean Pleistocene also related to the geodynamic, palaeoclimatic and palaeoceanographic conditions that favoured upwelling events and nutrients supply into the southern Adriatic basin.