Born in Chicago into a family of 14 children, Pelekoudas graduated from Crane Tech High School. He had an unsuccessful tryout with the St. Louis Cardinals as a player in 1934. He began umpiring while serving as an Army Special Services officer during World War II, and eventually worked his way up to the NL after stops in the Eastern Shore (1948), Interstate (1949), Western (1950–52) and Pacific Coast Leagues (1953–59). He worked in the World Series in 1966 and 1972, serving as crew chief the second time, and in the All-Star Game in 1961 (second game), 1967 and 1975. He also officiated in the National League Championship Series in 1969 and 1973. He is perhaps best remembered for ordering an apparent Hank Aaron home run nullified on August 18, 1965 because Aaron stepped out of the batter's box when he made contact; the umpire had warned Aaron on the previous two pitches. As a result, Aaron's home run record eventually stood at 755, instead of 756.
Pelekoudas was also the first umpire to eject Gaylord Perry from a game for using an illegal greasy substance on the ball. He was the home plate umpire when Willie Mays hit four home runs on April 30, 1961. He was the third base umpire when Sandy Koufax pitched his second no-hitter on May 11, 1963, and was the first base umpire for Koufax's perfect game on September 9, 1965. Pelekoudas umpired in six no-hitters in all, but was never behind the plate for one. He was also an umpire for the first game ever held at Shea Stadium on April 4, 1964.
Pelekoudas, who lived in Sunnyvale, California for most of his career, died there of heart failure at age 66, three weeks after suffering a stroke. He had married Jane Papangellin on April 28, 1946, and they had a daughter and a son; his brother Perry was also an umpire, working in the minor leagues, and his son Lee worked in the Seattle Mariners organization for 30 years. In the 1998 book Baseball's Golden Greeks by Diamantis Zervos, Jim Campanis describes a Greek moment in baseball when he was batting against Cincinnati Reds pitcher Milt Pappas, with Alex Grammas the third base coach and Pelekoudas calling balls and strikes behind the plate.
- National League 1968 Green Book, p. 26.
- "Obituaries". The Sporting News. 1985-01-07. p. 43.
- Dittmar, Joseph J. (1990). Baseball's Benchmark Boxscores. Jefferson, North Carolina: McFarland & Co. pp. 132–34. ISBN 0-89950-488-4.
- Coberly, Rich (1985). The No-Hit Hall of Fame: No-Hitters of the 20th Century. Newport Beach, California: Triple Play. p. 122. ISBN 0-934289-00-X.
- Coberly, p. 131.
- 1975 National League Green Book, p. 33.