Cancer stem cells (CSCs) are thought to be responsible for tumor relapse and metastasis due to their abilities to self-renew, differentiate, and give rise to new tumors. Cyclooxygenase-2 (COX-2) is highly expressed in several kinds of CSCs, and it helps promote stem cell renewal, proliferation, and radioresistance. Whether and how COX-2 contributes to CSC migration and invasion is unclear. In this study, COX-2 was overexpressed in the CSC-like side population (SP) of the human hepatocellular carcinoma (HCC) cell line HCCLM3. COX-2 overexpression significantly enhanced migration and invasion of SP cells, while reducing expression of metastasis-related proteins PDCD4 and PTEN. Treating SP cells with the selective COX-2 inhibitor celecoxib down-regulated COX-2 and caused a dose-dependent reduction in cell migration and invasion, which was associated with up-regulation of PDCD4 and PTEN. These results suggest that COX-2 exerts pro-metastatic effects on SP cells, and that these effects are mediated at least partly through regulation of PDCD4 and PTEN expression. These results further suggest that celecoxib may be a promising anti-metastatic agent to reduce migration and invasion by hepatic CSCs.