Williamina Paton Stevens nació el 15 de mayo de 1857 en Dundee, Escocia, hija de Robert Stevens y Mary Walker Stevens. Asistió a la escuela pública en Dundee hasta la edad de 14 años, luego dio clases dentro del sistema alumno-profesor hasta su matrimonio con James Fleming en 1877. La pareja emigró a Boston, Massachusetts, cuando ella tenía 21 años. Un año más tarde, cuando estaba embarazada de su hijo, Edward, James Fleming la abandonó. Williamina se vio obligada a buscar trabajo para mantenerse a sí misma y a su hijo Edward.
La fortuna sonrió a la madre soltera cuando le ofrecieron un empleo como sirvienta en la casa del profesor Edward Charles Pickering, director del Observatorio de Harvard. Pickering, un hombre brillante y motivado, que era también un visionario, estaba frustrado con sus empleados de sexo masculino en el Observatorio e hizo su famosa declaración «mi asistenta podría hacer un mejor trabajo». Resultó ser una declaración profética.
En 1881, Pickering le ofreció a Fleming un empleo temporal en el observatorio para hacer tareas rutinarias de oficina y algunos cálculos matemáticos, y pronto pasó a ser miembro permanente del personal de investigación. La pusieron a cargo de decenas de mujeres jóvenes, que fueron empleadas para hacer cálculos matemáticos, proceso que hoy en día hacen las computadoras, y las dirigía con una disciplina implacable, siendo temida y admirada a partes iguales. Además, corrigió todos los originales de las publicaciones del observatorio. Ayudó a elaborar un sistema de asignación de estrellas, que básicamente consistía en asignar una letra, que dependía de la cantidad del hidrógeno observado en su espectro. Las estrellas clasificadas con la letra A estaban formadas por hidrógeno casi en su totalidad, las clasificadas con la letra B contenían menos hidrógeno, y así sucesivamente. Este sistema le sirvió a Annie Jump Cannon como base de trabajo, el cual mejoró para desarrollar una clasificación basada en latemperatura. En los siguientes 30 años de su vida, colaboró en el análisis fotográfico de espectros estelares.
Fleming contribuyó en la confección del catálogo Henry Draper, y en un período de nueve años, catalogó más de 10.000 estrellas. En ese tiempo también descubrió 59 nebulosas gaseosas, 310 estrellas variables, y 10 novas. También estableció los primeros estándares fotográficos de magnitud usados para medir el brillo de las estrellas variables. En 1907, publicó un listado que contenía 222 estrellas variables que ella había descubierto, y en 1910, descubrió propiedades de los espectros de las enanas blancas, estrellas muy densas y muy calientes.
En 1888, Fleming descubrió la Nebulosa Cabeza de Caballo. William Pickering, quien tomó la fotografía, especuló que en aquel lugar había materia oscura oculta. En los artículos y libros siguientes Williamina Fleming no aparece en los créditos, ya que John Dreyer, el principal encargado de recopilar información para el primer Catálogo Índice, eliminó su nombre de la lista de objetos que descubrieron, atribuyendo todas las aportaciones a «Pickering». Sin embargo, en el segundo Catálogo Índice de 1908, Fleming recibió los créditos que le correspondían.
En 1899, Fleming recibió un título de Conservador del Archivo de Fotografías Astronómicas en Harvard, tratándose del primer cargo institucional en Harvard que se concedía a una mujer. En 1906, logró una plaza honoraria en el Royal Astronomical Society de Londres, siendo la primera mujer en ser elegida, y consiguió un premio honorario del Wellesley College. Poco después de su muerte, la Sociedad Astronómica de México la galardonó con la medalla Guadalupe Almendaro por el descubrimiento de nuevas estrellas.
Murió de pulmonía en Boston.
