Mental and physical (MAP) training targets the brain and the body through a combination of focused-attention meditation and aerobic exercise. The following feasibility pilot study tested whether 6 weeks of MAP training improves mental health outcomes, while enhancing discrimination learning and heart rate variability (HRV) in a group of women living with human immunodeficiency virus (HIV) and other stress-related conditions. Participants were assigned to training (n = 18) or no-training control (n = 8) groups depending on their ability and willingness to participate, and if their schedule allowed. Training sessions were held once a week for 6 weeks with 30 min of meditation followed by 30 min of aerobic exercise. Before and after 6 weeks of training, participants completed the Behavioral Pattern Separation Task as a measure of discrimination learning, self-report questionnaires of ruminative and trauma-related thoughts, depression, anxiety, and perceived stress, and an assessment of HRV at rest. After training, participants reported fewer ruminative and trauma-related thoughts, fewer depressive and anxiety symptoms, and less perceived stress (p\'s < 0.05). The positive impact on ruminative thoughts and depressive symptoms persisted 6 months after training. They also demonstrated enhanced discrimination of similar patterns of information (p < 0.05). HRV did not change after training (p > 0.05). Combining mental and physical training is an effective program for enhancing mental health and aspects of cognition in women living with HIV, although not necessarily through variance in heart rate.