Post-translational modifications of histones play important roles in chromatin structure and genomic stability. Distinct lysine residues in histones are targets for covalent binding of biotin, catalyzed by holocarboxylase synthetase (HCS) and biotinidase (BTD). Histone biotinylation has been implicated in heterochromatin structures, DNA repair, and mitotic chromosome condensation. To test whether HCS and BTD deficiency alters histone biotinylation and to characterize phenotypes associated with HCS and BTD deficiency, HCS- and BTD-deficient flies were generated by RNA interference (RNAi). Expression of HCS and BTD decreased by 65-90% in RNAi-treated flies, as judged by mRNA abundance, BTD activity, and abundance of HCS protein. Decreased expression of HCS and BTD caused decreased biotinylation of K9 and K18 in histone H3. This was associated with altered expression of 201 genes in HCS-deficient flies. Lifespan of HCS- and BTD-deficient flies decreased by up to 32% compared to wild-type controls. Heat tolerance decreased by up to 55% in HCS-deficient flies compared to controls, as judged by survival times; effects of BTD deficiency were minor. Consistent with this observation, HCS deficiency was associated with altered expression of 285 heat-responsive genes. HCS and BTD deficiency did not affect cold tolerance, suggesting stress-specific effects of chromatin remodeling by histone biotinylation. To our knowledge, this is the first study to provide evidence that HCS-dependent histone biotinylation affects gene function and phenotype, suggesting that the complex phenotypes of HCS- and BTD-deficiency disorders may reflect chromatin structure changes.