Johnson has described experiencing racial discrimination after joining the force, with white officers ostracizing him and on occasion referring to him and his fellow black officers as "niggers". By 1971 he had risen to the rank of sergeant, becoming the first black officer on the Birmingham force to hold that rank. The election in 1979 of Richard Arrington, the first black mayor of Birmingham, began an acceleration in racial integration of the force. Johnson was promoted together with Leroy Stover and John Fisher, the only other black sergeants on the force, to the rank of lieutenant in 1981.[5] In 1986 Johnson was promoted to captain, making him the first black on the force to hold that position.[6]
By 1991 Johnson had already made Deputy Chief. Arrington had previously brought in Arthur Deutcsh, a New Yorker, to run the force, however Deutcsh was forced to resign following his conviction for tampering with the arrest records of Richard Arrington's daughter, a conviction that was later overturned. Johnson was then picked to be acting police chief, a position he filled for roughly a year[5] before Arrington appointed Johnson as the force's first black chief of police in 1992.[7]
As Chief of Police, Johnson led efforts against domestic violence, and began a Citizen's Police Academy.[1]