This study investigates the role of recursive language and working memory (WM) in second-order false belief skills in Danish-speaking children with autism spectrum disorder (ASD; n = 62; 8 females) and typical development (n = 41; 15 females), ages 6-16. Second-order false belief skills correlated with receptive grammar, vocabulary, and age; sentential complement production predicted second-order false beliefs, controlling for age, receptive grammar and WM. Regressions showed that second-order false belief was associated with age across groups, but with sentential complements in the ASD group only. Second-order false belief skills improved in children who received training in "either" recursive phrases (d = 0.21) or WM (d = 0.74), compared to an active control group. Results suggest that false belief skills are entwined with both linguistic and executive functions.