Marine organisms are commonly under threats from various pathogens. Edwardsiella tarda is one of the fish pathogens that seriously infect cultured and wild fish species. Bacteremia caused by E. tarda can be a fatal disease in humans. Fish gill is a mucosa-associated lymphoid tissue that directly contacted with sea water. Generating gill transcriptomic resources that challenged by E. tarda is crucial for understanding the molecular mechanisms underlying gill immune responses. In this study, we performed transcriptome profiling of gene expression in Japanese flounder gills (Paralichthys olivaceus) challenged by E. tarda with different stress duration. An average of 40 million clean reads per library were obtained, of which approximately 83.2% were successfully mapped to the reference genome. 456 and 1037 differential expressed genes (DEGs) were identified at 8 h and 48 h post-injection, respectively. Gene annotation analysis and protein–protein interaction networks were conducted to obtain the key interaction relationships of immune-related DEGs during pathogens infection. 24 hub genes with multiple protein-protein interaction relationships or involved in multiple KEGG signaling pathways were discovered and validated by qRT-PCR. These hub genes mainly participated in Leukocyte transendothelial migration signaling pathway, B cell receptor signaling pathway, Wnt signaling pathway and Apoptosis signaling pathway. This study represents the first gill transcriptomic analysis based on protein–protein interaction networks in fish and provides valuable gene resources for understanding the fish gill immunity, which can pave the way to understand the molecular mechanisms of immune responses with E. tarda infection.