Natural antisense transcripts (NATs) have been shown to play important roles in post-transcriptional regulation through the RNA interference pathway. We have combined the pyrophosphate-based high-throughput sequencing and computational analysis to identify and analyze, in genome-scale, cis- and trans-NAT small RNAs that are derived under a normal condition and in response to drought and salt stresses in staple plant Oryza sativa. Out of a total of 714,202 sequence reads from high-throughput sequencing, we obtained 58,781, 43,003 and 80,990 unique small RNAs matching perfectly to the O. sativa genome, from the control, drought and salt libraries, respectively. Computationally, we identified 344 cis-NATs and 7,142 trans-NATs that are formed by protein-coding genes. From the deep sequencing data, we found 108 cis-NATs and 7,141 trans-NATs that gave rise to small RNAs from their overlapping regions. Consistent with early findings, the majority of these 108 cis-NATs seem to be associated with specific conditions or developmental stages. Our analyses also revealed several interesting results. The overlapping regions of the cis- and trans-NATs appear to be more enriched with small RNA loci than non-overlapping regions. The small RNAs generated from cis- and trans-NATs have a length bias of 21-nt, even though their lengths spread over a large range. Furthermore, more than 40% of the small RNAs from cis- and trans-NATs carry an 'A' as their 5' terminal nucleotides. A substantial portion of transcripts are involved in both cis- and trans-NATs, and many trans-NATs can form many-to-many relationships, indicating that NATs may form complex regulatory networks in O. sativa. Our work is the first genome-wide investigation of NAT-derived small RNAs in O. sativa. It revealed the importance of NATs in biogenesis of small RNAs, and broadened our understanding of the roles of NAT-derived small RNAs in gene regulation, particularly in response to environmental stimuli.