Rainbow trout Oncorhynchus mykiss is a cold-water species with considerable economic importance. A thermally selected strain was developed by selective breeding. The objective was to investigate genes related to upper temperature tolerance in rainbow trout by global gene expression analysis utilizing next generation sequencing. Fifty millions of paired sequences from gill tissues each of the thermally selected and Donaldson strains were assembled into transcripts. Global gene expressions in gills between the thermally selected and Donaldson strains were study in details. We integrated the data of both strains, identifying 13,092 independent known genes by BLASTX search. Then, we performed a back-mapping of raw reads from both strains onto the genes to investigate their frequency of expression. The 324 genes showed at least a 2-fold difference in the thermally selected strain compared with Donaldson strain, and 44.4% of commonly expressed genes were categorized into 38 functional groups by annotation. In addition to HSP genes, c-fos related genes were also highly expressed in the thermally selected strain. These results are useful to find genes responsible for upper temperature tolerance of rainbow trout.