Pierwszy rejs bojowy 1 grudnia 1941 roku okręt został przyporządkowany 7. Flotylli U-Bootów. 24 grudnia U-Boot wyszedł z Kilonii, udając się na swój pierwszy wojenny patrol na Atlantyk. 1 stycznia 1942 roku dowódca U-135, por. mar. Friedrich-Hermann Praetorius otrzymał awans na stopień kpt. mar. (niem. Kapitänleutnant). Od 6 do 20 stycznia okręt wchodził w skład wilczego stada . 22 stycznia o godzinie 22:21 w odległości około 420 Mm na wschód od przylądka Cape Race U-Boot storpedował marudera z konwoju ON-56, zbudowany w 1907 roku belgijski parowiec „Gandia” o pojemności 9626 BRT, płynący z ładunkiem 500 ton potażu z Liverpoolu do Saint John. Trafiony w rufę jedną z dwóch wystrzelonych torped statek zatonął po 10 minutach na przybliżonej pozycji , a z jego załogi składającej się z 79 osób uratowanych zostało zaledwie 14, wyłowionych z morza 5 lutego przez amerykański niszczyciel (ośmiu marynarzy i dwóch artylerzystów) oraz 17 lutego przez portugalski trawler motorowy „João Corte Real” (cztery osoby). 31 stycznia U-135 dopłynął do bazy w Saint-Nazaire, spędzając w morzu 39 dni.