Actinic keratosis (AK) is characterized by a reddish or occasionally skin-toned rough patch on sun-damaged skin, and it is regarded as a precursor to squamous cell carcinoma (SCC). Photodynamic therapy (PDT), utilizing 5-aminolevulinic acid (ALA) along with red light, is a recognized treatment option for AK that is limited by the penetration depth of light and the distribution of the photosensitizer into the skin. Cold atmospheric plasma (CAP) is a partially ionized gas with permeability-enhancing and anti-cancer properties. This study analyzed, in vitro, whether a combined treatment of CAP and ALA-PDT may improve the efficacy of the treatment. In addition, the effect of the application sequence of ALA and CAP was investigated using in vitro assays and the molecular characterization of human oral SCC cell lines (SCC-9, SCC-15, SCC-111), human cutaneous SCC cell lines (SCL-1, SCL-2, A431), and normal human epidermal keratinocytes (HEKn). The anti-tumor effect was determined by migration, invasion, and apoptosis assays and supported the improved efficacy of ALA-PDT in combination with CAP. However, the application sequence ALA-CAP–red light seems to be more efficacious than CAP-ALA–red light, which is probably due to increased intracellular ROS levels when ALA is applied first, followed by CAP and red light treatment. Furthermore, the expression of apoptosis- and senescence-related molecules (caspase-3, -6, -9, p16INK4a, p21CIP1) was increased, and different genes of the junctional network (ZO-1, CX31, CLDN1, CTNNB1) were induced after the combined treatment of CAP plus ALA-PDT. HEKn, however, were much less affected than SCC cells. Overall, the results show that CAP may improve the anti-tumor effects of conventional ALA-PDT on SCC cells. Whether this combined application is successful in treating AK in vivo has to be carefully examined in follow-up studies.