Diazotrophic bacteria were isolated from the rhizosphere of field-grown Triticum aestivum, Hordeum vulgare, and Avena sativa grown in various regions of Greece. One isolate, with the highest nitrogen-fixation ability from each of the eleven rhizospheres, was selected for further characterisation. Diazotrophic strains were assessed for plant-growth-promoting traits such as indoleacetic acid production and phosphate solubilisation. The phylogenies of 16S rRNA gene of the selected isolates were compared with those based on dnaK and nifH genes. The constructed trees indicated that the isolates were members of the species Azospirillum brasilense, Azospirillum zeae, and Pseudomonas stutzeri. Furthermore, the ipdC gene was detected in all A. brasilence and one A. zeae isolates. The work presented here provides the first molecular genetic evidence for the presence of culturable nitrogen-fixing P. stutzeri and A. zeae associated with field-grown A. sativa and H. vulgare in Greece.