When I heard the They Might Be Giants version when I was in high school, I was pretty surprised, since I'd heard my mom singing "Istanbul" since I was very small. TMBG just covered it (and they did a great version, mind, even better live). It was originally recorded by The Four Lads, and made the top ten in Billboard in 1953. The original lyrics were written by Jimmy Kennedy and the music by Nat Simon; TMBG kept the tune and modified the lyrics a little ("Miss-tanbul" is missing!).
You can probably win a free lunch from your friends by betting that the song isn't an original TMBG work, because hardly anyone under 50 seems to know this.