My wife's ancestors are from Galizien Kroenlande, Austria. I know that the surname has been changed, but her GGF was Felix Story/Storey. According to his New York City marriage license his father was John Story and his mother was Sophie Wojdyla. He married Mary Nalezna and her father was Adalbert and her mother was Eva Stelmach.

All we know is from the marriage license that lists Galicia Austria as the birthplace for both.

Any ideas on where to search back would be helpful.