In this Chapter, we discuss novel aspects of the depletion interaction, which arise in situations in which the large colloidal particles in the mixture are not hard but rather soft, penetrable spherical aggregates. Given the fact that true hard-sphere interactions are extremely challenging to realize experimentally, soft colloids are indeed the rule in complex, soft matter fluids, and not the exception. We adopt star polymers as prototypes of soft colloids and we consider depleting agents at the two extremes of the colloid-polymer spectrum: linear homopolymer chains, on the one hand, and small, hard spherical colloids, on the other. We analyze in detail the quantitative characteristics of the ensuing depletion interactions and we demonstrate that they have novel and unexpected features, stemming from the softness of the depleted particles and their penetrability to the additives. The implications of these characteristics on the thermodynamics and rheology of the mixtures are also critically discussed.