In order to collect Indonesian Nostoc, isolation of soil microflora from several paddy fields in West Java, Bali, and South Celebes was carried out. Fast-growing isolates of Nostoc were selected to describe and perform molecular identification using partial sequences of 16S rRNA. The results showed that partial sequences of 16S rRNA could not resolve the phylogeny of the isolates. However, it supported the morphological studies that recognize isolates as different species of Nostoc. Potential use of Nostoc as a nitrogen source for paddy growth was carried out using six strains as single inoculums. A total biomass of 2 g (fresh weight) for each strain was inoculated, respectively, into the pot planted with three paddy plants. This experiment was conducted in the green house for 115 days. Statistical analyses (ANOVA; α = 0.05) showed that of six strains tested in this study, only strain GIA13a had influence on the augmentation of root length and the total number of filled grains.