Po zakończeniu studiów, nie mając – ze względu na pochodzenie – większych szans na podjęcie pracy dydaktycznej, wyruszył w dłuższą podróż do Europy Zachodniej. Odwiedził ośrodki akademickie w Szwajcarii, Francji (Uniwersytet Paryski) i Wielkiej Brytanii (Uniwersytet Cambridge). Wszędzie zdobywał sławę jako doskonały i oryginalny matematyk, pełny nowatorskich pomysłów. W 1934 r. był pierwszym mężczyzną, który wygłosił wykład w College’u Girton.
W 1935 r. Ulam otrzymał zaproszenie na Uniwersytet Princeton w Stanach Zjednoczonych, w tym okresie zaprzyjaźnił się z von Neumannem i spotkał z Einsteinem. Po rocznym tam pobycie dostał propozycję dołączenia do organizacji i pracy na Uniwersytecie Harvarda, z której skorzystał. W tym czasie każde wakacje spędzał w Polsce – ostatni jego pobyt w rodzinnym Lwowie miał miejsce latem 1939. W lecie 1937 zaprosił do Polski von Neumanna, by wygłosił we Lwowie wykład. Gość zawitał kilka razy do Kawiarni Szkockiej. W 1939 r. trzyletni kontrakt w Society of Fellows wygasł bez możliwości przedłużenia go (ze względu na wiek Ulama). Dzięki George’owi Davidowi Birkhoffowi otrzymał pozwolenie na czasowe pozostanie na Harvardzie w charakterze wykładowcy na Wydziale Matematyki.