Robotic surgery provides many benefits such as reduced invasiveness and increased dexterity. This comes at the cost of no direct contact between surgeon and patient This physical separation prevents surgeons from performing direct haptic exploration of tissues and organs, imposing exclusive reliance on visual cues. Current technology is not yet able to both measure and reproduce a realistic and complete sense of touch (interaction force, temperature, roughness, etc.). In this paper, we put forward a concept based on multimodal feedback consisting of the integration of different kinds of visual and tactile cues with force feedback that can potentially improve both the surgeon's performance and the patient's safety. We present a cost-effective tactile display simulating a pulsating artery that has been integrated into a haptic work-station to combine both tactile and force-feedback information. Furthermore, we investigate the effect of different feedback types, including tactile and/or visual cues, on the performance of subjects carrying out two typical palpation tasks: (1) exploring a tissue to find a hidden artery and (2) identifying the orientation of a hidden artery. The results show that adding tactile feedback significantly reduces task completion time. Moreover, for high difficulty levels, subjects perform better with the feedback condition combining tactile and visual cues. As a matter of fact, the majority of the subjects in the study preferred this combined feedback because redundant feedback reassures subjects in their actions. Based on this work, we can infer that multimodal haptic feedback improves subjects' performance and confidence during exploratory procedures.