Gender disparities continue to exist in women's control, inheritance, and ownership of land in spite of legislation directing improvements in women's land access. Women are often excluded from traditional patrilineal inheritance systems, often lack the legal know-how or enforcement mechanisms to ensure their property rights are maintained, and often lack initial capital or asset bases to purchase land through market mechanisms. Community-based legal aid programs have been promoted as one way to expand access to justice for marginalized populations, through provision of free legal aid and education. Despite promising programmatic experiences, few rigorous evaluations have studied their impacts in developing countries. We evaluate the effect of a one-year community-based legal aid program in the Kagera Region of northwestern Tanzania using a randomized controlled trial design with specific attention to gender. We measure impacts of access to legal aid on a range of land-related knowledge, attitude, and practice outcomes using individual questionnaires administered to male and female household members separately. Effects were limited in the short term to settings with minimal transaction costs to the paralegal. Treatment women in smaller villages attend legal seminars and are more knowledgeable and positive regarding their legal access to land. Cost-effectiveness analysis shows that the costs of bringing about these changes are moderate. The difference between the impact of the intervention on men and on women is narrowed when taking into account the gender-differentiated paralegal effort, and thus costs, allocated to women and men.