Suspensions of soft particles with short-range attractive interactions are found in many industrial formulations, ranging from food and pharmaceuticals to cosmetics and advanced materials, such as toothpaste and mayonnaise. These particles exert short-range attractive interactions by hydrophobic alkyl chain extensions that can form sticky contacts with other hydrophobic alkyl chain due interactions of the extensions with other neighboring particles. These attractions lead to a weak network structure that increases the material’s yield stress and alters its flow behavior. Undergoing shear deformation, these sticky suspensions show flow instabilities such as shear banding. With increased stickiness, a more non-linear velocity profile is observed. Given this flow behavior, several questions arise regarding the ability of these suspensions to suspend a single rigid particle under its weight in shear flow. In this work, we perform particle dynamics simulations to study the sedimentation of a single rigid particle in a sheared suspension of soft, sticky ones. We examine how interparticle attraction affects the critical applied force required to initiate sedimentation and how this threshold varies with shear rate. Our results show that stickiness not only increases the resistance to sedimentation but also modifies the local flow field near the rigid particle compared to the non-attractive case and the contacts are more uniformly distributed due to the sticky nature. Finally, a stability diagram is constructed to map the transition between stable and sedimenting states as a function of shear rate and applied force at varying degrees of stickiness.