Harrell was born on January 30, 1944, to musician parents in Manhattan, New York City: his father was the baritone Mack Harrell, from Texas, and his mother, Marjorie McAlister Fulton, was a violinist, originally from Oklahoma. At the age of nine, he began cello studies. When he was 12, his family moved to Dallas, Texas, where he studied with Lev Aronson while his father taught at Southern Methodist University. Summers were often spent in Colorado, where his father was one of the founders and then the second director of the Aspen Music Festival and School.