Cognitive remediation (CR) programs are new to substance treatment and research needs to evaluate their implementation. The context of implementation, specifically staff perceptions, is critical to changing practice. The aim of this study was to identify treatment staff members' perceptions about the benefits and challenges of a new CR intervention in their workplace. The study conducted semi-structured interviews with staff at a residential substance treatment center when the CR program was first being implemented and again six months later. The study interviewed eight staff members in each round (>50% of staff members in the unit) from all role designations. A critical perspective shaped a thematic analysis of challenges to implementation. The study identified benefits of the CR program to clients and staff. However, only one staff member participated in training to deliver the program. In principle, staff members support the program, but this does not necessarily translate into active involvement, even when the study conducted staff engagement activities. CR programs are likely to improve functional outcomes for people in substance rehabilitation programs. However, this study suggests that staff accepting and valuing a new intervention is not enough to sustain it. For CR programs to be feasible, management should schedule and support staff training, and facilitate staff participation in that training. Organizational factors are likely to play a significant role in implementation success or failure, and further research should explore how the organizational culture of alcohol and other drug services impacts the implementation of CR therapy.