Z astronavtom Davidom Leestmo je zunaj plovila preživela tri ure in 29 minut, med katerimi sta preizkušala tehnologijo za oskrbovanje satelitov z gorivom v orbiti. Sullivan se je ameriški vesoljski agenciji NASA pridružila leta 1978, ko je bila izbrana v prvo skupino ameriških astronavtov, ki je vključevala tudi ženske. Pred tem je študirala geologijo in oceanografijo, pozneje pa sodelovala pri razvoju opreme in postopkov za delo v vesolju.

Njena prva vesoljska misija STS-41G se je začela 5. oktobra 1984. Challenger je v orbito ponesel sedemčlansko posadko, kar je bilo takrat največ ljudi na enem vesoljskem plovilu. Na krovu sta bili tudi dve ženski, Kathryn Sullivan in Sally Ride, prva Američanka v vesolju. Vesoljski sprehod je bil načrtovan kot preizkus postopkov za oskrbovanje satelitov z gorivom. Sullivan in Leestma sta uporabljala sistem Orbital Refueling System, s katerim je NASA raziskovala možnosti servisiranja vesoljskih plovil neposredno v orbiti.

Pred izstopom je bilo treba odpraviti tudi organizacijske in tehnične zaplete. Zaradi težav z anteno raketoplana so vesoljski sprehod prestavili na poznejši del misije. NASA je pred poletom obravnavala tudi vprašanja prilagajanja ženskega telesa nižjemu tlaku v vesoljskih skafandrih, vendar so za astronavtke in astronavte nazadnje veljali enaki postopki priprave.

Sullivan sicer ni bila prva ženska na vesoljskem sprehodu. Ta dosežek je 25. julija 1984 pripadel sovjetski kozmonavtki Svetlani Savicki, ki je med poletom na vesoljsko postajo Saljut 7 zunaj postaje preživela približno tri ure in pol. Challenger se je po osmih dneh v vesolju vrnil na Zemljo 13. oktobra 1984. Sullivan je pozneje sodelovala še pri dveh misijah raketoplanov, med drugim pri poletu STS-31 leta 1990, ko je posadka Discoveryja v orbito namestila vesoljski teleskop Hubble.

Po koncu astronavtske kariere je delovala na področju znanosti in oceanografije. Leta 2020 je postala tudi prva ženska, ki je obiskala najglobljo znano točko svetovnih oceanov, Challenger Deep v Marianskem jarku.