Kubina started his professional career with HC Vítkovice of the Czech Extraliga. He played there for four seasons, during which he was drafted in the seventh round, 179th overall, of the 1996 NHL Entry Draft by the Tampa Bay Lightning.
He then spent most of the 1997-98 season in the NHL, tallying a total of 21 points, while playing occasionally in the International Hockey League for the Cleveland Lumberjacks. By the 1999-00 NHL season, Kubina had cemented his position in the Lightning's lineup, and notched 26 points for them. Kubina had 30 points in the 2000-01 campaign and 34 in 2001-02. In 2003-04, Kubina scored 17 goals and 35 points in 81 games, a career high at that point. The Lightning also went on to win the Stanley Cup as NHL champion.
On July 1, 2006, Kubina signed a deal with the Toronto Maple Leafs for four years at $20 million. Kubina was suspended by the NHL for the first game of the 2006-07 season for cross-checking Detroit's Jiri Hudler in a preseason game. Kubina had his best statistical season of his career in 2007-08, where he scored 11 goals and 40 points in 72 games for the Maple Leafs.