From Lakeville, Minnesota, Nellie and her six siblings grew up on a dairy farm near Hinckley, Minnesota. Her father was a member of the Non-Partisan League, a radical rural organization. Johnson grew up with a strong tradition of support for education. Her mother and grandmother were teachers with an interest in political philosophy. Her father was a school board member in Dakota County.
At age 13, Johnson distributed Non-Partisan League flyers on her way to and from school. She graduated from Hinckley High School and left home at 17 to finish high school through the GED program at the University of Minnesota. After a number of years in the work force, Nellie continued her studies at the University of Wisconsin using the money she earned from trapping to finance her education there. For over 30 years, she has owned and operated Nellie's Alterations in downtown Minneapolis. Johnson's commitment to education continued through her work on the Minnesota Higher Education Board.
She has had a long and distinguished record of public service in support of the advancement of minority concerns, the rights of workers, and equal opportunities for all people. As a leader of organized labor in the 1930s and 1940s, she was the first woman vice-president of the Minnesota Culinary Council and the first woman vice-president of Local 665 Hotel and Restaurant Employees Union. She was also the first Black person elected to citywide office in Minneapolis when she won a seat on the Library Board in 1945. She also served on the Minnesota State University Board for eight years, and the Minnesota State Colleges and Universities board of Trustees. Johnson was the inspiration for one of the nameless bronze sculptures, titled "Shadow Spirits." The statues represent individuals who contributed to the development of Minneapolis and are symbolic of persons who disappear or are omitted from the pages of our history.
The W. Harry Davis Foundation honored Johnson in 1988 for her service to the community. Johnson's many contributions were featured in the book "Contributions of Black Women to Minnesota History". The "Nellie Stone Johnson Scholarship" was founded in 1989. It is awarded annually to minority students from union families. In 1995, she received an honorary doctoral degree from St. Cloud State University.
Johnson was a life member of the NAACP and the National Council of Negro Women; a member of the National Coalition of Labor Women, the National League of Women Voters, the DFL Affirmative Action Commission, and the DFL Feminist Caucus, a former board member of the Minneapolis Urban League, and recipient of the Urban League's Cecil E. Newman Humanitarian Award. Nellie Stone Johnson who grew up to become one of the most influential forces in the civil rights and labor movements in Minnesota, died on April 2, 2002; she was 96.