We focus on using evidence for making access control decisions in ubiquitous computing environments. These environments create new interaction scenarios that traditional access control approaches handle poorly. Our approach views access control as the filtering of messages between communicating services. Services are known only by name, and each service makes access control decisions based on local policies and evidence it gathers about other services. We implement our evidence-based approach with a mechanism analogous to a network firewall, filtering messages going to and from a service. Our evidence-based firewall is responsible for managing evidence, laying a foundation for extensions to it that gather, trade, and evolve evidence over time. This organization leads to an ecosystem of evidence providers that evolve as technology and markets develop. We describe the design of our evidence-based access model, discuss usagescenarios, and present preliminary results. The results suggest that this approach is flexible enough to accommodate interesting ubiquitous computing scenarios and efficient enough to implement on small devices.