Individuals differ in their physiological responsiveness to stressful challenges, and stress potentiates the development of many diseases. Heart rate variability (HRV), a measure of cardiac vagal break, is emerging as a strong index of physiological stress vulnerability. Thus, it is important to develop tools that identify predictive markers of individual differences in HRV responsiveness without exposing subjects to high stress. Here, using machine learning approaches, we show the strong predictive power of high-dimensional locomotor responses during novelty exploration to predict HRV responsiveness during stress exposure. Locomotor responses are collected in two ecologically valid virtual reality scenarios inspired by the animal literature and stress is elicited and measured in a third threatening virtual scenario. Our model's predictions generalize to other stressful challenges and outperforms other stress prediction instruments, such as anxiety questionnaires. Our study paves the way for the development of behavioral digital phenotyping tools for early detection of stress-vulnerable individuals.