Nell'ottobre 1986 venne assegnato al Johnson Space Center a Houston dove lavorò come un controllore di volo dei sistemi meccanici e il capo operazioni per il carrello di atterraggio, i freni e la barriera di emergenza dello Space Shuttle. Walheim venne trasferito nell'agosto 1989 al quartier generale dell'Air Force Space Command a Colorado Spring dove fu il manager di un programma per l'aggiornamento dei radar da avvertimento (warning radar). Venne selezionato per la scuola di pilotaggio nel 1991 e frequentò i corsi alla base aerea Edwards in California nel 1992. In seguito fu assegnato al programma F-16 Combined Test Force e dopo comandante dell'avionica e degli armamenti. Nel gennaio 1996 Walheim divenne istruttore alla scuola di pilotaggio dell'aeronautica, dove lavorò fino ad iniziare l'addestramento da astronauta.
Walheim durante la prima EVA nella missione STS-122
Walheim durante la seconda EVA nella missione STS-122
Walheim iniziò la carriera alla NASA come controllore di volo e ingegnere delle operazioni al Johnson Space Center dall'ottobre 1986 al gennaio 1989. Fu selezionato come candidato astronauta nel 1996 e dopo due anni di addestramento e valutazione fu certificato per il volo spaziale come specialista di missione. Inizialmente venne assegnato a compiti tecnici all'Astronaut Office Space Station Operations Branch. Partecipò alla missione STS-110 nel 2002 dove effettuò delle attività extraveicolari. Dopo il primo volo, venne assegnato alle attività extraveicolari, e fu selezionato per la missione STS-122 del febbraio 2008. In quest'ultima missione partecipò a tutte le tre passeggiate spaziali per un totale di oltre 22 ore di attività extraveicolare.
