Pseudomonas stutzeri is a potential candidate for bioremediation of selenium-contaminated grounds and waters. Here, we report the complete genome sequence of a novel strain, F2a, which was isolated from a seleniferous area of Punjab, India. The genome sequence provides insight into the potential selenium oxyanion-reducing activity of this strain.