The long term success of a human-robot interaction will depend on how comfortable and safe a human feels with it. But which feature of a robot’s movement determines human comfort? To address this question, here we considered four different models of human discomfort. We then designed an empirical human-robot co-worker task that enables us to both, quantify the discomfort experienced by the human co-worker by analyzing behavioral changes, and examine which model of discomfort explains the changes best. Using this task, we show that the perceived uncertainty in a robot’s movement is a key determinant of human discomfort, and we discuss how movement uncertainty can give a unified explanation for the modulation of human comfort with robots, and trust in them, as reported in several previous studies.