Harrelson was born in 1961 in Midland, Texas, to Diane (née Oswald) and Charles Voyde Harrelson. He has two brothers, Jordan and Brett Harrelson. In 1973, Harrelson moved to his mother's native city, Lebanon, Ohio, where he attended Lebanon High School. He spent the summer of 1979 working at Kings Island amusement park.
He attended Hanover College in Hanover, Indiana, where he joined the Sigma Chi fraternity. He received a Bachelor of Arts in theater and English in 1983. He told Playboy in October 2009: "I was getting into theology and studying the roots of the Bible, but then I started to discover the man-made nature of it. I started seeing things that made me ask, 'Is God really speaking through this instrument?' My eyes opened to the reality of the Bible being just a document to control people. At the time I was a real mama's boy and deeply mesmerized by the church."
His father, Charles Voyde Harrelson, was a convicted contract killer, who received a life sentence for the 1979 killing of Federal Judge John H. Wood Jr. in San Antonio, Texas. He died in the United States Penitentiary Administrative Maximum Facility on March 15, 2007.