Wiosną 1964 podczas podróży do Europy wystąpił w angielskim klubie nocnym Brentwood Folk Club. W następnych miesiącach kilkukrotnie wracał do Anglii, gdzie rozwijał karierę solową pod pseudonimem Paul Kane i występował w lokalnych klubach folkowych. W maju 1965 nagrał dla Columbia Records swój pierwszy solowy album pt. The Paul Simon Songbook, który poniósł sprzedażową klęskę na brytyjskim rynku. W tym okresie pracował także jako producent nagrań i autor piosenek dla innych wykonawców, a także odbył samodzielną trasę koncertową po Europie. W marcu 1969 otrzymał nagrodę Grammy za nagranie roku („Mrs. Robinson”) i najlepszą ścieżkę dźwiękową (soundtrack do filmu Absolwent), a w kwietniu wydał singiel „The Boxer”. W latach 70. prowadził wykłady z techniki pisania piosenek na Uniwersytecie Nowojorskim.
W sierpniu 1970 na stadionie Shea w Nowym Jorku zagrał pierwszy samodzielny koncert po rozpadzie duetu Simon & Garfunkel, występując na festiwalu upamiętniający 25. rocznicę ataku atomowego na Hiroszimę. W marcu 1971 na 13. gali rozdania nagród Grammy otrzymał statuetki za: nagranie roku i piosenkę roku („Bridge Over Troubled Water”) oraz za album roku i najlepszą aranżację (Bridge Over Troubled Water).