This work presents a strategy for quantitating polycyclic aromatic hydrocarbons (PAHs) in smoked paprika samples. For this, a liquid chromatographic method with fluorimetric detection (HPLC-FLD) was optimized. To resolve some interference co-eluting with the target analytes, the second-order multivariate curve resolution-alternating least-squares (MCR-ALS) algorithm has been employed combined with this liquid chromatographic method. Among the eight PAHs quantified (fluorene, phenanthrene, anthracene, pyrene, chrysene, benzo[a]anthracene, benzo[b]fluoranthene, and benzo[a]pyrene) by HPLC-FLD, only in the case of fluorene, pyrene, and benzo[b]fluoranthene was it necessary to apply the second-order algorithm for their resolution. Limits of detection and quantitation were between 0.015 and 0.45 mg/kg and between 0.15 and 1.5 mg/kg, respectively. Good recovery results (>80%) for paprika were obtained via the complete extraction procedure, consisting of an extraction from the matrix and the cleanup of the extract by means of silica cartridges. Higher concentrations of chrysene, benzo[a]anthracene, benzo[b]fluoranthene, and benzo[a]pyrene were found in the paprika samples, with respect to the maximal amounts allowed for other spices that are under European Regulation (EU) N° 2015/1933.