Appropriate post-translational processing of collagen requires prolyl hydroxylation, catalyzed by the prolyl 3- (C-P3H) and prolyl 4- (C-P4H) hydroxylases is essential for normal cell function. Here we have investigated the expression, transcriptional regulation and function of the C-P3H and C-P4H families in melanoma. We show that the CP3H family exemplified by Leprel1 and Leprel2 are subject to methylation-dependent transcriptional silencing in primary and metastatic melanoma consistent with a tumour suppressor function. In contrast, although there is transcriptional silencing of P4HA3 in a sub-set of melanomas, the CP4H family members P4HA1, P4HA2 and P4HA3 are often over-expressed in melanoma, expression being prognostic of worse clinical outcomes. Consistent with tumour suppressor function, ectopic expression of Leprel1 and Leprel2 inhibits melanoma proliferation, whereas P4HA2 and P4HA3 increase proliferation and particularly invasiveness of melanoma cells. Pharmacological inhibition with multiple selective C-P4H inhibitors reduces proliferation and inhibits invasiveness of melanoma cells. Together, our data identify the C-P3H and C-P4H families as potentially important regulators of melanoma growth and invasiveness and suggest that selective inhibition of C-P4H is an attractive strategy to reduce the invasive properties of melanoma cells.