Objectives: Whereas smoke-free housing (SFH) has the potential to protect residents from tobacco smoke, evidence suggests that SFH could lead to increased indoor smoking. In this study, we examine how perceptions of a residential smoking ban could be related to non-compliance. Methods: We conducted 8 focus group interviews of low-income housing residents living in Norfolk, Virginia (N=53). Interviews were semi-structured and based on a list of guided questions related to SFH compliance, developed in partnership with a standing community advisory board comprised of low-income housing residents. Results: Several themes emerged, including pervasive non-compliance, perceived unfairness and shame, barriers to compliance, and distrust of the housing authority. Smokers reported behavior primarily motivated by punishment avoidance, rather than out of any perceived obligation to comply with the ban. Conclusions: Results led us to consider Procedural Justice Theory as a conceptual framework, in which compliance is directly related to perceptions about the legitimacy of a rule or authority. When compliance is low due to a lack of perceived legitimacy, SFH should be adapted to promote changes in smoking behavior. We offer specific theory-supported adaptations to SFH focused on trust-building and improving perceived fairness.