After working in a Baton Rouge supermarket for almost three years, he was spotted by a father of a UNO baseball player while bagging groceries and was informed of Tim Floyd's lack of height on the basketball team at the University of New Orleans. Within a few days Johnson went to meet Floyd, who at first thought it was a joke. 
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.