Objective: To compare the effectiveness of different methods of recall for repeat Pap smear among women who had normal smears in the previous screening. Design: Prospective randomized controlled study. Setting: All community clinics in Klang under the Ministry of Health Malaysia. Participants: Women of Klang who attended cervical screening and had a normal Pap smear in the previous year, and were due for a repeat smear were recruited and randomly assigned to four different methods of recall for repeat smear. Intervention: The recall methods given to the women to remind them for a repeat smear were either by postal letter, registered letter, short message by phone (SMS) or phone call. Main Outcome Measures: Number and percentage of women who responded to the recall within 8 weeks after they had received the recall, irrespective whether they had Pap test conducted. Also the numbers of women in each recall method that came for repeat Pap smear. Results: The rates of recall messages reaching the women when using letter, registered letter, SMS and phone calls were 79%, 87%, 66% and 68%, respectively. However, the positive responses to recall by letter, registered letter, phone messages and telephone call were 23.9%, 23.0%, 32.9% and 50.9%, respectively (p<0.05). Furthermore, more women who received recall by phone call had been screened (p<0.05) compared to those who received recall by postal letter (OR=2.38, CI=1.56-3.62). Conclusion: Both the usual way of sending letters and registered letters had higher chances of reaching patients compared to using phone either for sending messages or calling. The response to the recall method and uptake of repeat smear, however, were highest via phone call, indicating the importance of direct communication.