KDM2A is a histone demethylase associated with transcriptional silencing, however very little is known about its in vivo role in development and disease. Here we demonstrate that loss of the orthologue kdm2aa in zebrafish causes widespread transcriptional disruption and leads to spontaneous melanomas at a high frequency. Fish homozygous for two independent premature stop codon alleles show reduced growth and survival, a strong male sex bias, and homozygous females exhibit a progressive oogenesis defect. kdm2aa mutant fish also develop melanomas from early adulthood onwards which are independent from mutations in braf and other common oncogenes and tumour suppressors as revealed by deep whole exome sequencing. In addition to effects on translation and DNA replication gene expression, high-replicate RNA-seq in morphologically normal individuals demonstrates a stable regulatory response of epigenetic modifiers and the specific de-repression of a group of zinc finger genes residing in constitutive heterochromatin. Together our data reveal a complex role for Kdm2aa in regulating normal mRNA levels and carcinogenesis. These findings establish kdm2aa mutants as the first single gene knockout model of melanoma biology.