He joined the Kingsport Mets in the rookie-level Appalachian League for the remainder of the season after his selection, and went 1-1 with a 7.45 ERA with a 2.14 WHIP over 17 games.

In 1989, Johnstone played with the Pittsfield Mets in the single-A New York-Penn League, posting an 11-2 record, a 2.77 ERA, and a 1.24 WHIP.

Johnstone started out the 1993 season with the triple-A Edmonton Trappers, going 4-15 with a 5.18 ERA and a 1.57 WHIP in the Pacific Coast League.

Despite these alarming figures, Florida called him up to join the parent club for the last month of the inaugural season.

On September 3, he made his MLB debut and took the loss, allowing an earned run in the 13th inning of a 5–4 decision against the Los Angeles Dodgers.

In 1994, Johnstone played most of the campaign back in Edmonton, going 5-3 with a 4.46 ERA in 29 games, striking out 43 in 42.1 innings along with a much improved 1.30 WHIP.

Johnstone labored at the triple-A level with the PCL's Tucson Toros in 1996, putting up a 3-3 record and a 3.42 ERA in 45 games.

He appeared in nine games with the Astros in the middle of the season, earning a 1-0 record and allowing 17 hits in 13 innings with a 5.54 ERA.

He earned an opening day victory on March 31, pitching two shutout innings at the end of a 12-inning 9-4 win over the Houston Astros.