On July 19, 1961, Malenko challenged "Nature Boy" Buddy Rogers for the NWA World title in Jacksonville, Florida, but was unsuccessful. On May 16, 1967, Malenko defeated Wahoo McDaniel to win the NWA Florida Heavyweight Championship in Tampa, Florida. On August 16, 1968, Malenko and Johnny Valentine defeated the team of Joe Scarpa (later known as Chief Jay Strongbow) and Jose Lothario for the NWA Southern Tag Team Championship titles, and four days later, Malenko defeated Eddie Graham for his first NWA Florida Brass Knuckles Championship in Jacksonville. Between 1968 and 1972, Malenko would win the Brass Knuckles title on seven more occasions, defeating the likes of Lothario, The Gladiator (Ricky Hunter), Strongbow (twice), Cyclone Negro, Bobby Duncum and Bearcat Wright.
On May 9, 1972, Malenko and Bob Roop defeated Bearcat Wright and Bobby Shane to win the NWA Florida Tag Team Championship, and six days later, Malenko defeated Wright in singles competition to win his eighth and final Florida Brass Knuckles title in Orlando. On June 24, 1972, Malenko and Johnny Weaver defeated Mike Webster and The Professional for his second run with the Florida Tag Team titles.
Malenko also wrestled in the Texas territory in the early 1970s, often teaming with Lord Charles Montegue (known as Hans Mortier from the WWF). Montegue also acted as Malenko's manager during this run in Texas.
During the early days of Verne Gagne's American Wrestling Association (AWA) territory, Malenko worked under the name Otto Von Krupp. He gained the AWA World Tag Team Championship with "Texas" Bob Geigel from Dale Lewis and Pat Kennedy (who wrestled elsewhere as Bobby "Hercules" Graham).
Malenko' wrestling name "The Great Malenko" was a pun; "Malenko" means "little" in Russian, and Boris was shorter than most of his fellow wrestlers.
Malenko has said on more than one occasion that Buddy Landel was the greatest thing he ever produced.
After retiring from the ring, Malenko opened a gym and training center, training wrestlers such as Buddy Landell, Barry Horowitz/Hart, Masked Superstar/Demolition Ax, Gangrel, Norman Smiley, Alex Gibson, Paul Diamond, Mark Hildreth, Perry Saturn, The Field Brothers, Sean Waltman (X-Pac), Tyree Pride, Crusher Doogan, and his own sons Dean Malenko and Joe Malenko and Fred Ottman, among others. He died in August 1994 of cancer.
Malenko was the inspiration for the title of Insane Clown Posse's fourth album, The Great Milenko, released in 1997.
- Finishing moves
- Russian Sickle (Lariat)
- Signature moves
- Biting the opponent
- Eye poke
- "The Great Malenko"
- "Professor Malenko"
Championships and accomplishments
- Championship Wrestling from Florida
- NWA Brass Knuckles Championship (Florida version) (8 times)
- NWA Florida Heavyweight Championship (1 time)
- NWA Florida Tag Team Championship (2 times) - with Bob Roop (1) and Johnny Walker (1)
- NWA Southern Heavyweight Championship (Florida version) (1 time)
- NWA Southern Tag Team Championship (Florida version) (1 time) - with Johnny Valentine
- Southeastern Championship Wrestling
- Southwest Sports, Inc. - NWA Big Time Wrestling