Low oxygen levels (hypoxia) play a role in clinical conditions such as stroke, chronic ischemia and cancer. To better understand these diseases, it is crucial to study the responses of vertebrates to hypoxia. Amongst vertebrates, some teleosts have developed the ability to adapt to extreme low oxygen levels. We have studied long-term adaptive responses to hypoxia in adult zebrafish. We used zebrafish which survived severe hypoxic conditions for three weeks and showed adaptive behavioral and phenotypic changes. We used cDNA microarrays to investigate hypoxia-induced changes in expression of 15,532 genes in the respiratory organs - the gills. We have identified 367 differentially expressed genes, 117 showed hypoxia-induced and 250 hypoxia-reduced expressions. Metabolic depression was indicated by repression of genes in the TCA cycle, in the Electron Transport Chain and of genes involved in protein biosynthesis. We observed enhanced expression of the monocarboxylate transporter (mct4) and of the oxygen transporter myoglobin. The hypoxia-induced group further included the genes for Niemann Pick C disease (NPC) and for Wolman-disease (Lysosomal acid lipase/LAL). Both diseases lead to a similar intra- and extra cellular accumulation of cholesterol and glycolipids. The NPC protein binds to cholesterol from internal lysosomal membranes and is involved in cholesterol trafficking. LAL is responsible for lysosomal cholesterol degradation. Our data suggest a novel adaptive mechanism to hypoxia, the induction of genes for lysosomal lipid trafficking and degradation. Studying physiological responses to hypoxia in species tolerant for extremely low oxygen levels can help identify novel regulatory genes which may have important clinical implications.