Like most neo-Nazi groups active in the United States today, the National Socialist Movement traces its roots back to the 1960s and George Lincoln Rockwell's American Nazi Party (ANP), the first well-established neo-Nazi organization in America. After Rockwell's assassination in 1967, a variety of neo-Nazi factions sprang up from the disorganized and fractious remnants of the ANP. One such group was a small neo-Nazi group started by two former Rockwell storm troopers, Robert Brannen and Cliff Herrington, in 1974. Operating under the dubious name of the National Socialist American Workers Freedom Movement, it was tiny and its influence did not extend much beyond its headquarters in South St. Paul, Minnesota.

During the 1970s, Brannen suffered multiple strokes and was succeeded by Herrington in 1983. Herrington (born in 1947) ran the group for over a decade, by which point it had expanded to only a handful of chapters outside of Minnesota. Before 1993, when Herrington and a fellow member showed up in Nazi uniform at a Minnesota legislative committee hearing to protest a proposed gay rights bill, the local media was largely unaware of their group's existence. However, by the mid-1990s, the group's presence, at least in the Twin Cities, was well-known, especially since some of its members enjoyed wearing their Nazi uniforms in public.

In 1994, Herrington stepped down from command though remained an active member in favor of his much younger second-in-command, Jeff Schoep. Schoep, born in 1973, had been active in the group from an early age and was more able to appeal to racist skinheads and other young white supremacists. He made his first splash in 1998 when trying to host a major white supremacist event. Prominent neo-Nazis such as Allen Vincent and Tom Metzger endorsed Schoep and his group, by then renamed the National Socialist Movement. Vincent said that Schoep had “great bloodlines” and predicted he would be able to unite the different white supremacist groups in the United States and make Minneapolis-St. Paul the “national headquarters” for the white revolution.