After working in a Baton Rouge supermarket for almost three years, Johnson played basketball at the University of New Orleans under coach Tim Floyd.
UNO recorded 87 victories during Johnson's time in the program. They earned two NCAA tournament bids and one NIT tournament appearance. When he finished, he was the second all-time leading scorer in UNO history (1,608 points), first all-time in field goal percentage (59%), first all-time in double-doubles with 55, first all-time in rebounds with 1,287 (10.5 per game), third all-time in double-figure scoring games (81), eighth all-time in steals (109), second all-time in games played (123) and first all-time in blocks (294). Johnson was named All-American South Conference for the 1990-1991 season, All-Sun Belt Conference for the 1991-1992 season and was the 1992-1993 Sun Belt Conference Player of the Year.
Johnson was named Basketball Times 2nd Team All-American for 1992-93 and 3rd team All-American by Basketball Weekly and United Press International. He was named Honorable Mention All-American for the same season by the Associated Press.
Johnson was named MVP of the NABC All-America Game in 1993.