Gibbs started his Rugby career at Pencoed RFC at mini and youth level, his first class career started at Bridgend RFC during the 1990/91 season, followed by a short spell at Neath RFC, before making his Welsh debut in 1991 against England. However he moved to Swansea RFC in January 1992, scoring a try on his debut in a Cup game against Oakdale. Gibbs also scored further tries that season in the cup against Neath RFC and Newport RFC to help Swansea reach the final where they lost to Llanelli RFC at Cardiff Arms Park.
Despite being only 22, he was selected for the 1993 British Lions tour to New Zealand, where he impressed so much that he was selected for the second and third tests instead of then-England captain Will Carling.
In 1994 Gibbs left union to join rugby league team St Helens.
On his return to union in 1996 it was sometimes joked that he was the fastest prop in world rugby, though in fact he was an inside centre. He became known as the world's hardest tackler (summed up by his nickname "Car-Crash") and this was exemplified by his performance in his second Lions tour.
In 1997 Gibbs was a key member of the victorious British and Irish Lions tour of South Africa. The Springboks were at the time the world champions following the 1995 World Cup and were expected to win the series. However, the Lions produced some memorable defensive performances with Gibbs at the centre of the action pulling off some devastating tackles.
In the defining moment of the series, Gibbs crashed through the Springboks' key player, 19-stone Os du Randt on one of his trademark bullocking runs. The Lions went on to win the series 2–1 and Gibbs was voted "Player of the Series".
In later years Gibbs was sometimes criticised for being too one-dimensional but he did show startling agility to claim the winning try in the last-ever Five Nations match in 1999. Wales were playing England at Wembley with England trying to complete the Grand Slam. England led by 6 points with 3 minutes left to play and appeared to have won the game but in one of the last plays of the match, Gibbs received a Scott Quinnell pass 20m from the try line and proceeded to 'sidestep' one player for one of the most celebrated tries in Welsh history. (In a 2013 article for The Guardian, Gibbs said that the play was inspired by a move that his old St Helens teammate Bobbie Goulding had regularly used to great success in the 13-man code, namely packing the midfield with forwards before allowing a back to cut through on a diagonal dummy run.)  Following Neil Jenkins' conversion, Wales won the match 32–31 in what is agreed to be one of the best matches played in the competition and caused England not only to miss out on the Grand Slam, but handed the last ever Five Nations Championship to Scotland.