Identifying effective and accessible interventions for family caregivers of persons with dementia (PWD) is crucial as the prevalence of dementia increases in Asia. This study investigated the efficacy of a telephone-intervention on the reduction in caregiver burden, as well as depressive and anxiety symptoms among family caregivers (FCs) of PWD in Malaysia. A single-blinded randomized controlled trial was carried out with 121 FCs of PWD selected from memory or psychiatry clinics in three tertiary hospitals in Malaysia, who were randomly allocated into the intervention or control group. The intervention group received the psychoeducational intervention delivered by healthcare staff via telephone for 10 sessions over 12 weeks. The outcome of the intervention was measured by the Malay version of the Zarit Burden Interview and the Hospital Anxiety and Depression Scale at baseline and post-intervention. An intention to treat analysis shows that caregiver burden, anxiety symptoms, and psychological distress among FCs in the intervention group decreased by 7.57 units (p < 0.001), 2.46 units (p < 0.001), and 2.98 units (p = 0.011), respectively, at post-intervention, compared to the differences from baseline to post-intervention in the control group. Policies aimed at integrating the telephone-intervention into memory/psychiatry clinics in Malaysia may help FCs of PWD to reduce their caregiver burden and stress while caring for a family member with dementia.