Williamina Paton, as she was born, came from Dundee and worked for several years as a schoolteacher. In 1877 she married James Fleming and emigrated with him to Boston, Massachusetts, in 1878. Her marriage broke up and, forced to support her young son, she worked for Edward Pickering, director of the Harvard College Observatory, as a maid. As it was his policy to employ young women at the observatory as computers, Pickering, who quickly recognized her intelligence, offered her temporary employment as a copyist and computer in 1879. She was given a permanent post in 1881. She remained at the observatory for the rest of her life, serving as curator of astronomical photographs from 1899 until her death.

She worked with Pickering on the basic classification of stars into spectral types and was thus involved in the introduction of the original 17 classes arranged alphabetically from A to Q in terms of the intensity of the hydrogen spectral lines. This system was later modified and improved by her colleagues Annie Cannon and Antonia Maury.

Fleming was largely responsible for the classification of over 10,000 stars, published in 1890 in the Draper Catalogue of Stellar Spectra. In the course of her work she discovered 10 novae and over 200 variable stars, and estimated that by 1910 she had examined nearly 200,000 photographic plates.