The area of Human-Robot Interaction deals with problems not only related to robots interacting with humans, but also with problems related to humans interacting and controlling robots. This dissertation focuses on the latter and evaluates multi-sensory (vision, hearing, touch, smell) feedback interfaces as a means to improve robot-operator cognition and performance. A set of four empirical studies using both simulated and real robotic systems evaluated a set of multi-sensory feedback interfaces with various levels of complexity. The task scenario for the robot in these studies involved the search for victims in a debris-filled environment after a fictitious catastrophic event (e.g., earthquake) took place. The results show that, if well-designed, multi-sensory feedback interfaces can indeed improve the robot operator data perception and performance. Improvements in operator performance were detected for navigation and search tasks despite minor increases in workload. In fact, some of the multi-sensory interfaces evaluated even led to a reduction in workload. The results also point out that redundant feedback is not always beneficial to the operator. While introducing the concept of operator omni-directional perception, that is, the operator’s capability of perceiving data or events coming from all senses and in all directions, this work explains that feedback redundancy is only beneficial when it enhances the operator omni-directional perception of data relevant to the task at hand. Last, the comprehensive methodology employed and refined over the course of the four studies is suggested as a starting point for the design of future HRI user studies. In summary, this work sheds some light on the benefits and challenges multi-sensory feedback interfaces bring, specifically on teleoperated robotics. It adds to our current understanding of these kinds of interfaces and provides a few insights to assist the continuation of research in the area.