I was in Israel last summer and used my Blackberry Z30 on T-Mobile and it was friggin' awesome! Not the fastest data speeds but certainly good enough for email/text/light browsing. Best part was international data from T-Mobile was free so nothing to do but turn on the phone when you touched down.
Your S4 should have all the frequencies/bands you need for international but you should definitely do a bit of research to triple check.
Thanks for the info! It sounds you were definitely getting more than 2G, at least. I'm pretty sure the S IV GPE has the relevant bands, but I figured I would ask and see how it worked IRL.