Karen Miller was born 14 October 1958 in Topeka, Kansas. Miller's father was an aircraft mechanic in the United States Air Force, and the family lived in numerous places during her adolescence, including Washington State, Maryland, Germany, and England. When Miller was seventeen, her father retired from the military and they returned to the United States. After graduating high school in 1976, Miller worked in a bakery for a short time, before deciding she wanted to join the U.S. Navy to qualify for the GI Bill and attend college.

She spoke with a navy recruiter, enlisted in the delayed entry program, and chose occupational rating of data processing technician (DP). Miller was eventually sent to Naval Training Center Orlando, Florida, for basic training. After basic, Miller was sent to Naval Base San Diego, where she spent a few months learning to be a data processor. While in San Diego, Miller came out as a lesbian and began frequenting gay bars, and as a result, her grades began to suffer. When she was informed that she was being kicked out of the service, Miller pleaded to stay.

She was allowed to graduate but received low grades. Miller was then sent to Navy Yard, in Washington D.C., where she began working the night shift, loading computers with punch cards for programmers to work on. She eventually switched to the day shift. During this time, Miller was sent to Keesler Air Force Base in Biloxi, Mississippi, for data processing school. In 1979, Miller, now a E-3 Seaman, was assigned to the USS L. Y. Spear in Norfolk, Virginia; one of three women being allowed onboard a submarine tender for the first time.

She worked evenings on ship, but due to the inadequate military pay, Miller picked up extra jobs, including driving a cab, and selling Avon beauty products to other navy women. While on the ship, Miller began to become bothered by the intimidation and verbal abuse of the male seaman, and their never-ending belief that women can't do the same work as men. In 1981, while on the USS L. Y. Spear, and near Greece, Miller began getting very seasick, so they dropped her off, leaving her to find her own way back to the United States.

When she eventually made her way to the U.S. and Norfolk, Virginia, Miller was assigned temporary duty to the USS Land until her original ship returned. Miller left the U.S. Navy in 1981.