Construction robots are being used for several repetitive, basic tasks in construction sites, and soon it is expected that they will be used in more complicated operations to assist human workers. However, given the dynamic and unstructured nature of construction sites, robots’ engagement in complex tasks requires high intelligence and autonomy levels. While working with highly-automated robots in shared workspaces can result in higher productivity and lower costs, it may not be embraced by many construction workers, resulting in poor performance, safety, and well-being. Therefore, it is critical to profoundly understand workers’ response to imminent autonomous robots before their vast implementation at construction sites. In this context, effective measurement of workers’ cognitive load provides insights into human responses to robotic co-workers. Therefore, this study investigates the impact of autonomy levels of construction robots on workers’ cognitive load using qualitative and quantitative methods. To that end, an experiment was conducted in which subjects performed a masonry task in two different scenarios in collaboration with a semi-autonomous and an autonomous robot. An immersive virtual environment was used as a controlled and safe testbed to examine workers’ cognitive load while working alongside a virtual construction robot. Subjects’ electroencephalography (EEG) signals and questionnaires (NASA-TLX) were collected to assess cognitive load during each scenario. The results indicated that subjects’ cognitive load increased with an increase in the robot autonomy level, suggesting incorporating human factors in designing collaborative robots. The findings can help to determine adequate autonomy levels for seamless human–robot collaboration at construction sites.