In 1985, Anderson debuted in World Championship Wrestling with uncle Ole Anderson as The Minnesota Wrecking Crew. The team quickly became a force in the promotion by capturing the WCW Tag Team Championship in March 1985. Arn and Ole defended the titles throughout the year, with their highest profile match being part of the card for Starrcade 1985 on Thanksgiving night. The Crew successfully defended the titles against Wahoo McDaniel and Billy Jack Haynes.
In the latter half of 1985, the Andersons formed a loose knit alliance with fellow heels Tully Blanchard and Ric Flair, as they began to have common enemies. The foursome frequently teamed together in six-man, and sometimes, eight-man tag matches or interfered in each other's matches to help score a victory or, at least, to prevent each other from losing their titles. The alliance quickly became a force within the territory, working in feuds against some of the biggest stars in the company like Dusty Rhodes, Magnum T.A., The Road Warriors and the Rock 'n' Roll Express. Anderson also saw success as a singles wrestler on January 4, 1986 by winning the vacant WCW Television Championship. Simultaneously, Anderson was still one half of the WCW Tag Team Champions and, even though WCW abandoned the initial version of the tag titles in March, Anderson's success as a dual champion elevated his status within the territory. It was also during this time (in 1986) that the Andersons, Blanchard, and Flair began calling themselves The Four Horsemen with James J. Dillon serving as the group's manager. Anderson also had a tremendous ability to do interviews to further the storylines he participated in. His ability to improvise in interviews allowed him to coin the "Four Horsemen" moniker for the stable, as he likened their coming to wrestle at an event and the aftermath of their wrath as being akin to the Four Horsemen of the Apocalypse, and the name stuck. Anderson continued his reign as WCW Television Champion for most of the year, holding the championship for just over 9 months before losing it to Dusty Rhodes on September 9, 1986.
The first real setback with the Horsemen occurred at Starrcade 1986 after Anderson and Ole lost a Steel Cage match to The Rock 'n' Roll Express, with Ole getting pinned. The subsequent storyline positioned Ole as the weak link within the team, possibly attributed to his age. Ole's position with the group was only further weakened after he decided to take two months off after Starrcade. After Ole's return in February 1987, the other Horsemen turned on him and threw him out of the group, resulting in Ole incurring numerous attacks over the next several months. Afterwards, Ole was replaced with Lex Luger and the Horsemen resumed their dominance of the company.
As a member of the Horsemen, Anderson continued to be involved in high-profile angles within the company. By mid-1987, Anderson and fellow Horseman Tully Blanchard began regularly competing as a tag team and rose quickly through the tag team ranks. The duo faced the Rock 'n' Roll Express for the WCW World Tag Team Championship on September 29, 1987 and were victorious. This win further solidified the group's dominance in the company as Lex Luger was the reigning WCW United States Heavyweight Champion and Ric Flair spent most of 1987 as the WCW World Heavyweight Champion, losing it to Ron Garvin in September, only to regain it at Starrcade 1987 on Thanksgiving night. Anderson and Tully continued to feud throughout the rest of the year and first few months of 1988 with the Road Warriors, the Rock 'n' Roll Express and the Midnight Express being their most frequent rivals.
By December 1987, Luger had defected from the Horsemen and began a heated feud with the group, with Ric Flair especially. In early 1988, Luger formed a tag team with Barry Windham and began challenging Anderson and Blanchard for the WCW World Tag Team Championship. The bigger, stronger team of Windham and Luger were eventually successful, winning the titles on March 27, 1988. The reign would be short lived, however, as Anderson and Blanchard regained the titles less than a month later after Barry Windham turned on Luger during their match and joined the Horsemen. Their last contracted match with the company took place on September 10, 1988 when they dropped the WCW World Tag Team Championship to the Midnight Express before leaving for the WWF.
Anderson and Blanchard left WCW to join Vince McMahon's World Wrestling Federation in 1988. Upon being named the Brain Busters, the team took Bobby "The Brain" Heenan as their manager and quickly began rising through the tag team ranks, eventually coming to challenge Demolition for the WWF Tag Team Championship. On July 18, 1989, the Brain Busters won the titles, ending Demolition's historic reign of 478 days; the match would air on the July 29 edition of Saturday Night's Main Event. Although they would lose the titles back to Demolition just over three months later, the Brain Busters continued to be a force in the WWF's tag team division.
In December 1989, Anderson left the WWF and went back to WCW. Anderson helped to reform the Horsemen and he quickly found success in the company, winning the WCW World Television Championship on January 2, 1990. Anderson remained the champion almost the entire year before dropping it to Tom Zenk. Zenk's reign would be short lived, however, as Anderson regained the title. His third reign with the title was also considered successful as he held the title a little more than five months before dropping it to "Beautiful" Bobby Eaton on May 19, 1991. Afterwards, with Horsemen members Ric Flair and Sid Vicious gone to the WWF and Barry Windham having turned face, Anderson entered the tag team ranks of WCW.
In the summer of 1991, Anderson formed a tag team with Larry Zbyszko and they called themselves The Enforcers. After competing for several months and moving up in the tag team ranks, they successfully captured the WCW World Tag Team Championship on September 2, 1991. The reign would be short lived, however, as they lost the titles roughly two and a half months later to Ricky Steamboat and Dustin Rhodes. Anderson and Zbyszko went their separate ways shortly afterward. Anderson quickly rebounded from his split with Zbyszko and formed a tag team with Beautiful Bobby Eaton, a long-time friend and best known for his time as one half of the Midnight Express. At this point, they were members of Paul E. Dangerously's Dangerous Alliance. They quickly moved up the tag team division and were soon a threat to Steamboat and Rhodes. Anderson and Eaton quickly won the titles on January 16, 1992 and defended the titles against all comers for the next four and a half months before losing the titles to The Steiner Brothers in May.
In May 1993, Anderson joined Ole Anderson and Ric Flair to re-form the Four Horsemen. The Horsemen introduced Paul Roma as their newest member. Although Anderson and Roma won the WCW World Tag Team Championship in August, the group quickly split and was seen as a dismal failure by WCW.
Anderson remained a regular, on-screen performer in WCW over the next few years. He wrestled as a face, even teaming with Dustin Rhodes to feud with the Stud Stable. However he turned heel again and betrayed Rhodes by rejoining Col. Rob Parker's Stud Stable in 1994 with Terry Funk, Bunkhouse Buck, "Stunning" Steve Austin and Meng. The Stud Stable feuded heavily with Dusty and Dustin Rhodes until late 1994 when Funk left. In early 1995, Meng eventually left to join the Dungeon of Doom.
Anderson's last championship run began on January 8, 1995 after winning the World Television Championship from Johnny B. Badd. Anderson helped restore the prestige of the title, which he held for just over six months before dropping it to The Renegade. He briefly feuded with long-time friend Flair, and was assisted by Brian Pillman in his efforts. However, it was a swerve to reunify the Horsemen with Flair, Anderson, Pillman, and a partner to be named later (who ended up being Chris Benoit).
By the end of 1996, Anderson rarely competed in the ring as years of wear and tear on his body finally started to catch up with him. On the November 25 edition of Nitro, Anderson fought Luger to a double count-out in a quarter-final tournament match for the vacant WCW United States Championship.
On the August 25, 1997 episode of Monday Nitro, Anderson formally announced his retirement from the ring. While standing in the ring, surrounded by Ric Flair and newest Horsemen members Steve McMichael and Benoit, Anderson declared that his last official act as the "Enforcer" for the Four Horsemen was to offer his "spot" in the group to Curt Hennig, as he was forced to retire due to extensive neck and upper back injuries. He worked a couple tag matches afterward, including teaming with David Flair on an episode of WCW Thunder, but his physical involvement was extremely limited in those bouts.
On the September 14, 1998 edition of Nitro, alongside Steve McMichael, Dean Malenko, and Chris Benoit, Anderson ceremoniously reintroduced Ric Flair to WCW after his 12-month hiatus. In doing so, they reformed the Horsemen who then feuded with WCW President Eric Bischoff. Flair won the presidency of WCW from Bischoff on the December 28, 1998 episode of Nitro followed by winning the WCW World Heavyweight Championship at Uncensored 1999 and turn heel in the process. Anderson remained Flair's right-hand man during this time as he attempted to keep Flair's delusional hunger for power at bay.
In 2000, Anderson was a member of the short-lived Old Age Outlaws. Led by Terry Funk, the group of veteran wrestlers battled the revived New World Order. WCW was purchased by the World Wrestling Federation in 2001, ending Anderson's tenure there.
Not long after the closing of WCW, Anderson became a road agent for the WWF, renamed World Wrestling Entertainment (WWE) in May 2002. He occasionally appeared on WWE television trying to, with the help of other WWE management, pull apart (kayfabe) backstage brawls. Before the WCW/ECW Invasion storyline, Anderson took up color commentary for a WCW World Heavyweight Championship match between Booker T and Buff Bagwell, the WCW Cruiserweight Championship match with Billy Kidman and Gregory Helms as well as another WCW Championship match between Diamond Dallas Page and Booker T, which would be his only appearances as a commentator in WWE. He made an appearance on Raw in 2002 delivering a video to Triple H before he was supposed to renew his wedding vows to then-heel, Stephanie McMahon. Anderson was also assaulted on Raw by The Undertaker leading up the Undertaker vs. then-babyface Ric Flair match at WrestleMania X8. During that bout, Anderson made a brief in-ring appearance, delivering his signature spinebuster to The Undertaker. He would later turn heel once again by helping Ric Flair in his feud with Stone Cold Steve Austin, leading to Austin (kayfabe) urinating on him. Several months later he became a face once again and attempted to help a then-babyface Flair gain (kayfabe) sole ownership of WWE during a match with Vince McMahon, but backed down from a confrontation with Brock Lesnar, who entered the ring to assist McMahon.
Anderson made a special appearance at the October 2006 Raw Family Reunion special, in which he was in Ric Flair's corner for his match against Mitch of the Spirit Squad. Anderson was in the corner of Flair, Sgt. Slaughter, Dusty Rhodes, and Ron Simmons at Survivor Series 2006, where the four faced the Spirit Squad, but was ejected from the arena during the match. On the March 31, 2008 Raw, Anderson came out to say his final goodbye to Ric Flair and thank him for his career. At the No Mercy event, he was backstage congratulating Triple H for retaining the WWE Championship against Jeff Hardy.
In 2012, Arn was inducted into the WWE Hall of Fame as part of the Four Horsemen (along with Tully Blanchard, Ric Flair, Barry Windham, and J.J. Dillon).
On an episode of SmackDown Live in August 2016, Anderson made an appearance as one of the people asked by Heath Slater to be his tag team partner for the tournament to determine the inaugural winners of the WWE SmackDown Tag Team Championship. Anderson refused to help Slater upon learning that he was not Slater's first choice as a tag team partner. On the August 8, 2017 episode of SmackDown Live, Anderson made a guest appearance on The Fashion Files, revealing himself to be the one who destroyed Breezango's toy horse, Tully, and boasting he was the best horse from the Four Horsemen, and that "Tully" should have been named "Arn". On February 22, 2019, it was reported Anderson had been released from the WWE.
On August 3, 2024, Anderson made his WWE return at SummerSlam in a backstage segment during Cody Rhodes' entrance.