Randle had 65 touchdown catches in 120 games during his career, currently placing him 12th on the NFL's all-time TD-per-game list (minimum 60 TDs). His 65 TD catches were also the most in the NFL during the 1960s; Don Maynard caught 84 and Lance Alworth caught 77 in the American Football League (AFL).
On November 4, 1962, Randle had one of the biggest games statistically by a wide receiver in NFL history as he caught 16 passes for 256 yards in a game against the New York Giants. Randle finished the 1962 season with 63 receptions for 1,158 yards and eight touchdown catches and was named second-team All-Pro by UPI.
Randle once again passed the 1,000-yard receiving mark in 1963, finishing with 1,014 yards on 51 catches, eight of which went for touchdowns.
After his retirement in 1968, Randle became an assistant coach at East Carolina where, after one season, he became the Pirates' head coach, a job he held from 1971 through 1973. He then spent two years as head coach at his alma mater, the University of Virginia (1974–1975), two seasons at Massanutten Military Academy (1976–1977), and five seasons at Marshall (1979–1983).