Pigeon pea is an ideal crop for sustainable agriculture systems in Karst areas of southwest China, which frequently suffers from the formidable water deficit. Physiologically, arbuscular mycorrhizae (AM)-colonized pigeon pea (Cajanus cajan) demonstrated a further enhanced tolerance to drought stress. To elucidate the molecular mechanism underlying the elevated tolerance, suppression subtractive hybridization (SSH) were employed to dig up the differentially expressed genes using mixed cDNAs prepared from drought-stressed and unstressed pigeon pea seedlings inoculated by AM fungi (AMF) in the present work. Both forward and reverse SSH cDNA library were constructed and a total of 768 clones were obtained. Dot-blotting expression analysis identified that 142 clones were upregulated, and 49 were downregulated during water stress. After sequencing, 182 unique expressed sequence tags (ESTs) were obtained via blast analysis, among which 142 (78%) exhibited high homology to previously identified or putative proteins, however, 40 (22%) showed no homology in the database. The upregulated (102) and downregulated (40) ESTs with significant protein homology might be sorted into 16 and 12 functional categories respectively, which involved in a broad spectrum of biological pathways. Furthermore, semi-quantitative reverse transcription (RT)-PCR was carried out for the 35 differentially expressed genes whose putative functions implicated in abiotic stress tolerances in other species, and it was verified these differentially expressed genes highly involved in drought stress tolerance of AM-colonized pigeon pea.