Melissa Stone was the Fiance of Tony During the first four episodes of the first season and daughter of General Stone.

In the piolot she gives Tony a kiss before she goes into space, later Jeannie tried to cause trouble by making Melissa think Tony was being unfaithful. Later on she and her father go over to tonys and find him in arabic atire and dancing girls (thank's to Jeannie). But the leave the house on good terms.

On their wedding day her childhood friend returns and she decides to marry him instead of Tony. Much to his relief as things were starting to get controlling on her side such as choosing his own best man and lieing about their honeymoon.