The gasotransmitter hydrogen sulfide (H2S) produced by the transsulfuration pathway (TSP) is an important biological mediator, involved in many physiological and pathological processes in multiple higher organisms, including humans. Cystathionine-β-synthase (CBS) and cystathionine-γ-lyase (CSE) enzymes play a central role in H2S production and metabolism. Here, we investigated the role of H2S in learning and memory processes by exploring several Drosophila melanogaster strains with single and double deletions of CBS and CSE developed by the CRISPR/Cas9 technique. We monitored the learning and memory parameters of these strains using the mating rejection courtship paradigm and demonstrated that the deletion of the CBS gene, which is expressed predominantly in the central nervous system, and double deletions completely block short- and long-term memory formation in fruit flies. On the other hand, the flies with CSE deletion preserve short- and long-term memory but fail to exhibit long-term memory retention. Transcriptome profiling of the heads of the males from the strains with deletions in Gene Ontology terms revealed a strong down-regulation of many genes involved in learning and memory, reproductive behavior, cognition, and the oxidation–reduction process in all strains with CBS deletion, indicating an important role of the hydrogen sulfide production in these vital processes.