Henriksen found work as a muralist and as a laborer on ships. For a time, he worked in Europe. His first theater work, around age 30, was as set designer, and he received his first acting role because he built the set for a production. Illiterate until then, it was around this time that he taught himself to read. For his first role, he put the entire script to tape with the help of a friend, learning everyone's part in addition to his own. Soon afterward, he graduated from the Actors Studio and began acting in New York City.