Nienstedt was ordained a priest on July 27, 1974, in the United States. He then served as an associate pastor at Guardian Angels Parish in Clawson until 1976. He became secretary to Cardinal John Francis Dearden and a part-time professor of moral theology at St. John's Provincial Seminary in Plymouth in 1977. He was also a weekend associate pastor at St. Fabian's Parish in Farmington Hills and at Our Lady of Sorrows Parish in Farmington. He became vicar general for the Archdiocese of Detroit in 1979. He accompanied Cardinal Dearden to the August 1978 papal conclave, where he met the future Pope John Paul II.