Our previous study revealed that the miR-199 family (miR-199a-5p/-3p and miR-199b-5p/-3p) acts as tumor-suppressive miRNAs in head and neck squamous cell carcinoma (HNSCC). Furthermore, recent studies have indicated that the passenger strands of miRNAs are involved in cancer pathogenesis. The aim of this study was to identify cancer-promoting genes commonly regulated by miR-199-5p and miR-199-3p in HNSCC cells. Our in silico analysis and luciferase reporter assay identified paxillin (PXN) as a direct target of both miR-199-5p and miR-199-3p in HNSCC cells. Analysis of the cancer genome atlas (TCGA) database showed that expression of PXN significantly predicted a worse prognosis (5-year overall survival rate; p = 0.0283). PXN expression was identified as an independent factor predicting patient survival according to multivariate Cox regression analyses (p = 0.0452). Overexpression of PXN was detected in HNSCC clinical specimens by immunostaining. Functional assays in HNSCC cells showed that knockdown of PXN expression attenuated cancer cell migration and invasion, suggesting that aberrant expression of PXN contributed to HNSCC cell aggressiveness. Our miRNA-based approach will provide new insights into the molecular pathogenesis of HNSCC.