Time-based prospective memory (PM) is diminished under various task demands in individuals with autism spectrum disorder (ASD). However, it is still unclear what underpins their impairment or how it could be remediated. This study explored whether instructions to prioritise one element of a PM task over another improved performance in adults with ASD (compared to a group of matched neurotypical adults), and how that is related to cognitive abilities. Results indicated that importance instructions significantly improved the PM performance of participants with ASD. Moreover, the extent of the benefit was associated significantly with objectively-measured executive set-shifting ability and self-reported inhibitory control ability (the poorer the set-shifting/inhibitory control, the greater the benefit). Implications for future research and clinical practice are discussed.