A lot of the actors from TOS were on Bonanza -- DeForest K was in one playing a doctor!
Also, a lot of the female guest stars were on Bonanza, too.
The "big three" of TOS were in Gunsmoke as well. I've seen them all on DVD but had to IMDB them to find the years.
DeForest Kelley - 1956. I own this DVD (Gunsmoke seasons 1 - 4) and IIRC, I didn't recognize Kelley the first time I saw it for three reasons:
-I wasn't expecting to see Dr. McCoy in a black & white Gunsmoke episode
-He wore a cowboy hat
-He also wore an Abe Lincoln style beard - a full beard but no mustache.
Interesting trivia I just found while looking this up at imdb.com:
Kelley played Ike Clanton in a 1955 episode of You Are There called The Gunfight At The OK Corral.
Link
But wait, there's more!
Kelley also played Morgan Earp in a 1957 movie with Burt Lancaster and Kirk Douglas called Gunfight At The OK Corral.
Link
Leonard Nimoy - 1961, '62, '63, and '66. I've seen the 1966 episode in which Nimoy convincingly played an Indian and wore a black wig with long braids.
William Shatner - 1966. Like the Nimoy '66 episode, I saw this on a DVD borrowed from the library and don't remember much about this episode.