Children's responses to new, unfamiliar social interactions should be influenced by their cognitive appraisals and physiology, though little is known about how these constructs interrelate. To investigate these links, we examined whether children's appraisals of recalled events and resting parasympathetic physiology predicted social problem-solving behavior during a novel social interaction structured lab task. A diverse sample of 184 children 4 to 11 years old (M[subscript age] = 7.70 years, SD = 2.30; 50.5% girls) encountered an unfamiliar researcher who behaved oddly and wore a scary mask. Contrary to expectations, overall appraisals did not predict social problem-solving behavior. However, an exploratory analysis revealed that previously having made a prior challenge appraisal of an "angry" autobiographical experience predicted greater social problem-solving behavior. As anticipated, higher resting physiology was associated with more social problem-solving. This study provides initial insight into how appraisals and physiology shape children's behavior and influence their ability to tackle real-world social problems.