Rice has developed several morphological and physiological strategies to adapt to phosphate starvation in the soil. In order to elucidate the molecular basis of response to phosphate starvation, we performed mRNA sequencing of 4 rice cultivars with variation in growth response to Pi starvation as indicated by the shoot/root dry weight ratio. Approximately 254 million sequence reads were mapped onto the IRGSP-1.0 reference rice genome sequence and an average of about 5,000 transcripts from each cultivar were found to be responsive under phosphate starvation. Comparative analysis of the RNA-Seq profiles of the 4 cultivars revealed similarities as well as distinct differences in expression of these responsive transcripts. We elucidated a set of core responsive transcripts including annotated and unannotated transcripts commonly expressed in the 4 cultivars but with different levels of expression. De novo assembly of unmapped reads to the Nipponbare genome generated a set of sequence contigs representing potential new transcripts that may be involved in tolerance to phosphate starvation. This study can be used for identification of genes and gene networks associated with environmental stress and the development of novel strategies for improving tolerance to phosphate starvation in rice and other cereal crops.