This study examined the accuracy and costs of determining whether rural, low-income Medicaid recipients did or did not have a phone, and of obtaining phone numbers for those who did. For a random sample of 209 families, we compared phone information obtained from phone books and directory assistance with information obtained from department of social services (DSS) records. DSS records identified 51% of the sample as having phones, compared with 19%-25% for phone books and directory assistance. For identifying families as having no home phone or a phone with a number that matched the one in the DSS record, phone books or directory assistance corresponded with DSS records in 52%-57% of the sample. Using phone books or directory assistance was up to 3.2 times more costly than using DSS records. The study highlighted the need to establish policies to promote the exchange of information between social services and public health agencies and researchers.