Johnson returned to the ballroom on 19 March for Season 4, this time partnered with member of N'Sync Joey Fatone. She became the runner-up professional dancer of this season. After the completion of Dancing with the Stars, Johnson and Joey Fatone celebrated by going on the inaugural Mediterranean cruise for the Disney Cruise Line. The two performed for the ship's guests on 2 June 2007. Billionaire Mark Cuban was her Season 5 Partner. They were voted off in the fifth week. In season 6 she competed with magician Penn Jillette, but they were the first voted off in the Double-Elimination in the second week. Johnson competed on season 7 partnered with former NFL Player Warren Sapp. They finished in second place behind Brooke Burke and Derek Hough. This was Johnson's second time being the professional runner-up.