Interaction of olfactory receptor (OR) genes with environmental odors is regarded as the first step of olfaction. In this study, OR genes of two fish, medaka (Oryzias latipes) and stickleback (Gasterosteus aculeatus), were identified and an evolutional analysis was conducted. The selection pressure of different TM regions and complete coding region were compared. Three TM regions (TM4, TM5 and TM6) were found to have higher average Ka/Ks values, which might be partly caused by positive selection as suggested by subsequent positive selection analysis. Further analysis showed that many PTSs overlap, or are adjacent to previously deduced binding sites in mammals. These results support the hypothesis that binding sites of fish OR genes may evolved under positive selection.