Recent developments in human–robot interaction (HRI) research have heightened the need to incorporate indirect human signals to implicitly facilitate intuitive human–guided interactions. Eye-gaze has been widely used nowadays as an input interface in multi-modal teleoperation scenarios due to their advantage in revealing human intentions and forthcoming actions. However, to date, there has been no discussion about how the structure of the environment, that the human is interacting with, could affect the complexity of the teleoperation task. In this paper, a new metric named “Scene-oriented Task Complexity Metric” (SoTCM) is proposed to estimate the complexity of a certain scene that is involved in eye-gaze-supported teleoperation tasks. The proposed SoTCM objectively estimates the effort that could be exerted by the human operator in terms of the expected time required to point at all the informative locations retrieved from the scene under discussion. The developed SoTCM depends on both the density and distribution of the informative locations in the scene, while incorporates the eye movement behavior found in the psychology literature. The proposed SoTCM is subjectively validated by using the time-to-complete index in addition to the standard (NASA-TLX) workload measure in eight varying structure scenes. Results confirmed a significant relation between SoTCM and the measured task workload which endorses the applicability of using SoTCM in predicting scene complexities and subsequently the task workload in advance.