Photodynamic therapy is a potentially curative treatment for various types of cancer. It involves energy transfer from an excited photosensitizer to surrounding oxygen molecules to produce cytotoxic singlet oxygen species, a process termed as type II reaction. The efficiency of photodynamic therapy is greatly reduced because of the reduced levels of oxygen, often found in tumor microenvironments that also house cancer stem cells, a subpopulation of tumor cells that are characterized by enhanced tumorigenicity and resistance to conventional therapies. We show here that encapsulation of a photosensitizer, methylene blue, in alginate-Aerosol OT nanoparticles leads to an increased production of reactive oxygen species (ROS) under both normoxic and hypoxic conditions. ROS generation was found to depend on the interaction of the cationic photosensitizer with the anionic alginate polymer. Dye-polymer interaction was characterized by formation of methylene blue dimers, potentially enabling electron transfer and a type I photochemical reaction that is less sensitive to environmental oxygen concentration. We also find that nanoparticle encapsulated methylene blue has the capacity to eliminate cancer stem cells under hypoxic conditions, an important goal of current cancer therapy.