- NWA (Mid America) Southern Tag Team titles w/Golden Hawk defeating Rex Mobley & Henry Harrell (April 17, 1952);
- NWA Pacific Northwest Heavyweight title defeating Moondog Mayne (July 22, 1967);
- NWA Pacific Northwest Tag Team titles w/Jim Osborne defeating Moondog Mayne & Tony Borne (August 10, 1967);
- NWA Pacific Northwest Tag Team titles w/Dean Ho defeating Moondog Mayne & Tony Borne (September 6, 1967);
- NWA (Vancouver) Canadian Tag Team titles w/Don Leo Jonathan defeating Stan Stasiak & Dutch Savage (September 23, 1968);
- Arizona Heavyweight title defeating Jody Arnold (????, 1969);
One of the greatest angles ever involving Kostas came in Arizona around 1970. Johnny was in a feud with regional villain, Jody Arnold, and always wrestled in his bare feet. Anyway, in a promo before their bout, Kostas came on screen during the TV taping with a large box, with a question mark in it. He announced in his box was a secret weapon that would help him beat Arnold. Naturally, fans had to come to see what was in the box. The box contained nothing but a pair of wrestling boots which Kostas put on and wore during the bout. Arnold was supposedly so worried the boots were loaded with something or so rattled to see Kostas not wrestling in his bare feet, the psychological impact was too much for him and he lost quickly.. Arnold would later reflect that Kostas, along with Ray Gordon, was legitimately the toughest man he ever wrestled or trained with.
Though a mainstay in the Arizona-California region, Kostas also appeared in Europe, Australia, Canada, Mexico, South America, the Pacific Northwest and the Northeastern USA. Kostas spoke several languages, including English, Spanish, Greek and French.
Greg Kelly wrote: Here are John Kostas’ Sydney results for 1965 —– 65/6/26- John Kostas d Pat O’Hara. 7/3- John Kostas d Al Woods. 7/10- Spiros Arion & John Kostas d Mitsu Arakawa & Bob the Bruiser DQ. 7/17- Spiros Arion & John Kostas d Mitsu Arakawa & Bob the Bruiser 2-0. 7/24- Spiros Arion/John Kostas/Dick Steinborn d Bob the Bruiser/Killer Kowalski/Mitsu Arakawa 2-1. 7/31- Roy Heffernan d John Kostas. 8/7- Alaskan d John Kostas. 8/14- Bulldog Brower d John Kostas. 8/21- Bob the Bruiser d John Kostas. 8/28- Cyclone Negro d John Kostas.
Dale Pierce wrote: In old Portland results, Johnny Kostas has the distinction of facing and beating a wrestkler who went under the name of Kay Faben (an inside joke obviously. Details as to who this was? Who knows????)