Joseph O. Stenoien was born in 1916 in Superior, Wisconsin. The son of a Lutheran Brethren Church minister, Stenoien was the eldest of 10 children. The family moved to North Dakota, then to Minnesota. Stenoien attended the North Dakota State Teachers College, most likely receiving a teacher's certification. After graduating, he taught high school science for a short period. During World War II, Stenoien enlisted in the Navy and married Irene Renk. After the war, the couple moved to Spokane, Washington, where Joseph continued to serve in the Naval Reserve for two years. His daughter Karen was born in Spokane in late 1945.

The family moved to Kirkland, Washington, in 1947 so Joseph Stenoien could attend the University of Washington, majoring in physics. At UW, Stenoien worked on the cyclotron and his Masters thesis was written about it. He received his MS in 1951 and began working for Boeing shortly after in the company's Physical Research Unit. During this time, Stenoien published an article with two coworkers in the Journal of Applied Physics. Because his research could be used in classified work, Stenoien applied for a security clearance in 1952, which was denied. Stenoien concluded that the denial might be due to two factors: His participation in the Progressive Party campaign for Henry Wallace in 1948, and/or his association with family dentist Richard Nelson (d. 1964), an avowed communist.

With extensive help from his labor union, the Seattle Professional Engineering Employees Association (SPEEA, later renamed to the Society of Professional Engineering Employees in Aerospace), Stenoien appealed the clearance denial. At the time, SPEEA was a relatively new organization and used Stenoien’s case as a model for its later approach in defending employees in similar disputes. Additionally, Stenoien was also assisted by the Engineers and Scientists of America (ESA), a labor advocacy group with connections to SPEEA, in his security clearance appeals process. Under the leadership of Security Chairman Floyd Hamilton, an electrical engineer at Boeing, and president Joseph Amann, the ESA provided legal assistance in many similar cases during the McCarthy Era.

The Western Industrial Personnel Security Board heard Stenoien’s appeal in San Francisco, California, on January 21-22, 1954. Joseph's wife, Irene Stenoien, and two other SPEEA members testified at the hearing, as well as Dorothy Lassers, the chair of the East Side Progressive Party. Dan Hendricks of SPEEA acted as counsel for Joseph. In an unusual decision for the McCarthy Era, the Board reversed its decision and granted Joseph a security clearance. As a result of this and the union's support, Boeing gave Stenoien his job back, including back pay.