A mathematical model for the transmission dynamics of human immunodeficiency virus (HIV) within a host is developed. Our model focuses on the roles of immune response cells or cytotoxic lymphocytes (CTLs). The model includes active and inactive cytotoxic immune cells. The basic reproduction number and the global stability of the virus free equilibrium is carried out. The model is modified to include anti-retroviral treatment interventions and the controlled reproduction number is explored. Their effects on the HIV infection dynamics are investigated. Two different disease stage scenarios are assessed: early-stage and advanced-stage of the disease. Furthermore, optimal control theory is employed to enhance healthy CD4+ T cells, active cytotoxic immune cells and minimize the total cost of anti-retroviral treatment interventions. Two different anti-retroviral treatment interventions (RTI and PI) are incorporated. The results highlight the key roles of cytotoxic immune response in the HIV infection dynamics and corresponding optimal treatment strategies. It turns out that the combined control (both RTI and PI) and stronger immune response is the best intervention to maximize healthy CD4+ T cells at a minimal cost of treatments.