Anthony "Tony" Nelson, is a major in NASA and is Jeannie's master. Tony is played by the great and late Larry Hagman and is one of Hagman's greatest works other than Dallas (TV Series)

Jeannie always pops in to Tony's office in NASA and lets Tony's boss  Colonel Dr. Alfred Bellows think he is crazy, but it turns out that when Dr. Bellows talks to the Maj. Gen. Martin Peterson about Nelson, the General thinks Dr. Bellows is going crazy instead.

Tony's best friend is Captain/Major Roger Healey. Roger is always trying to get Jeannie for his own use. He gets all nervous around Jeannie.