Unlike many of the "wrestlers" who have broken into the business in the last few years, Arn Anderson actually IS a wrestler. Before breaking into the business, he wrestled in the 167-pound weight class in high school in Rome, GA. One of Arn’s good friends was current WCW referee Randy "Pee Wee" Anderson, who wrestled in the 119-pound weight class at a rival high school. Ironically, at that time it was Randy who was the better wrestler as Randy went on to be a state champion. As high schoolers, Arn and Randy would regularly attend the local pro matches together. After high school, Arn became involved in powerlifting, adding 40 pounds of muscle to his frame. (Arn was oftern billed as having wrestled at the University of Minnesota to give credibility to Ole Anderson being his uncle.) Arn and Randy broke into the business at the same time, with Arn getting his first big break from Sylvester Ritter (The Junkyard Dog), who took a liking to Arn.

In the earliest parts of Arn's pro career, he wrestled under his real name. He made his debut in a taped-for-television match in Pensacola, FL, in January, 1982, losing to veteran "Bullet" Bob Armstrong. In those earliest months he got beaten pretty badly on a regular basis.

Arn moved to Louisiana with Bob Armstrong's help where he established a partnership with "Maniac" Matt Borne (who would later go on to somewhat dubious fame as "Doink the Clown"). With Matt Borne (from Ted Dibiase's Rat Pack) as his tag team partner, they moved to the NWA/Georgia area. Arn & Matt were managed by Paul Ellering and were billed as the top contenders for the vacant National Tag Team Titles (vacated by the Samoans). Arn and Matt were dumped by Ellering for the winners of the tournament; The Road Warriors. Matt & Arn split and Arn turned face & aligned himself with "Uncle" Ole and Tommy Rich to feud against The Road Warriors & Ellering's growing stable. This was in 1983.

In late 1983, Arn left Georgia (some reports say Borne was fired) and went to the NWA Southeast area (Alabama & Northern Florida), where he wrestled as Super Olympia with his partner Mr. Olympia (Jerry Stubbs). Super Olympia’s garb was a solid color mask with contrasting highlights around the mouth, nose, and eye holes and matching short black trunks. When he tagged with Mr. Olympia, they were matching outfits. After Anderson and Stubbs lost the masks to each other in separate matches with Stubbs losing his first, they still wrestled as a team and wore matching Panama hats. After Arn and Stubbs were unmasked, they won the vacant Southeast Tag Titles in a tournament. They won and lost the Southeast Titles three times throughout 1984. During this time, Arn came back to Georgia for a couple of dates to face his uncle "Pig-Face" Ole (his own words). Arn then feuded with Stubbs (now wrestling again as Mr. Olympia) after they split as team in late 1984 or early 1985. Arn was aligned w/Jimmy Golden (Bunkhouse Buck), Lord Humongous, Pat Rose and Bill Ash in the Tennessee Stud Stable managed by Ron Fuller, Robert's older brother (Robert Fuller is Colonel Robert Parker). In 1985 Arn and Pat Rose won the Southeast Tag Titles from the R.A.T. Pack (Scott & Steve Armstrong & Johnny Rich). Once they lost the titles back to them, Arn made his way into the Mid-Atlantic area, which was then merging with the Georgia area as World Championship Wrestling on TBS, where he began his feud w/Manny Fernandez and once again aligned himself with Ole.

The "winner take all" attitude of the Horsemen was present with Arn even in those early days. It is evidenced by this account from a fan during those days:

"I remember when Arn Anderson was Super Olympia in South AL/NW FL 15-20 years ago. One Friday night at the Houston County Farm Center in Dothan, he turned on tag team partner Jacques Rougeau and gave him a spinebuster. The next afternoon on TV he apologized profusely and begged Rougeau to give him another chance to be his partner that afternoon against the team they'd been wrestling the night before. Of course Rougeau (back then he was the Alabama champion and one of the big faces in that territory) ‘forgave’ him. After several minutes of the ensuing match, Rougeau was thrown out of the ring and Anderson/Super Olympia went out to him, gave him another spinebuster, and yelled "Sucker!" Great stuff."

Arn’s career turned the corner quickly when he began tag teaming with his uncle/cousin Ole Anderson. It's been pretty well established that Ole and Arn are not blood relatives, and it's often said that Ole is Arn’s father-in-law. So, they are in no way related by blood but they happen to look somwhat alike, with the same color hair and beards. Even though Ole, like all the Andersons, had historically been a rulebreaker, at this point in his career, Ole abided by the rules. A wild feud erupted between "uncle and nephew". When the dust cleared, Ole returned to his old ways and Arn became his tag partner.

Once they started teaming, Arn’s style was identical to Ole’s as he used the trademark of working on the left arm of an opponent, forcing him to submit before the arm was yanked right out of the socket. As great as they were, they only held one tag championship together, that being the prestigious Georgia National Tag Team Belts. The belts had been held by the team of Ole Anderson and Thunderbolt Patterson. How Arn and Ole came to hold the belts is a well documented piece of wrestling lore.

Ole and Thunderbolt were the Georgia National Tag Team Champions. Unfortunately for Thunderbolt, one night Ole informed Thunderbolt that he "had seen the future of professional wrestling", that being Arn. The following night, Ole interfered in Arn’s match with Manny Fernandez and Ole and Arn were double teaming Manny. Thunderbolt came to the ring to protest the carnage.

Arn blindsided Thunderbolt, threw him into the ring, and opened up a can of whup-ass on him. Ole hesitated at first, and then joined in the attack on Thunderbolt. Afterwards, he gave Thunderbolt’s tag team belt to Arn and told Thunderbolt that if he wanted the belts back, he could get a partner. Thunderbolt took Manny Fernandez on as his partner, but they were unsuccessful in a match held on April 28^th, 1985, and Arn and Ole were then officially the National Tag Team Champions. As National Tag Team Champions, they would go on to defeat Wahoo McDaniel and Billy Jack Haynes at Starrcade '85, handing that team their first loss ever.