Im Februar 1988 wurde Brown einer neuen Mission zugeteilt. Am 8. August 1989 flog er mit der Raumfähre Columbia zum ersten Mal ins All. STS-28 war ein Flug für das US-Verteidigungsministerium mit geheimer Nutzlast.
Am 12. September 1991 startete Brown mit der Raumfähre Discovery in den Weltraum. Bei dieser fünftägigen Mission wurde der UARS-Satellit zur Erforschung der oberen Atmosphäre ausgesetzt.
Brown verließ die NASA und Air Force im Juli 1993 und ging zur General Research Corporation (heute AT&T) nach Dayton (Ohio). Im Jahr 2003 wechselte Brown zur Computer Sciences Corporation (CSC) und ist dort Vizepräsident und General Manager für den Bereich Luft- und Raumfahrt.