Primetime Emmy Award for Outstanding Supporting Actress in a Comedy Series (1997) (for verk: 3rd Rock from the Sun, tema for: 49th Primetime Emmy Awards) Primetime Emmy Award for Outstanding Supporting Actress in a Comedy Series (1999) (for verk: 3rd Rock from the Sun, tema for: 51st Primetime Emmy Awards)
Johnston fikk sin profesjonelle scenedebut med New Yorks Atlantic Theater Company, som ble grunnlagt av David Mamet. I tillegg opptrådte hun med the Naked Angels Theater Company, og New York Stage and Film.
For sin opptreden i The Lights ved Lincoln Center Theatre ble Johnston nominert til en Drama Desk-pris som beste kvinnelige birolleinnehaver. En sjef ved Carsey-Werner Productions fikk øynene opp for Johnston etter prisutdelingen, og etter flere auditioner i 1996 til TV-serien Ti fingre og elleve tær vant hun rollen som «Sally Solomon», romvesenløytnanten og sikkerhetsoffiseren som utga seg for å være et sexy, kvinnelig menneske i Ohio. Hun opptrådte i serien fra 1996 til 2001 sammen med John Lithgow, Jane Curtin, French Stewart og Joseph Gordon-Levitt. Johnston ble nominert til Emmy-prisen tre år på rad for beste kvinnelige birolle i en komedieserie for rollen som «Sally Solomon», og hun vant i 1997 og i 1999.
