Po odejściu z armii w 1945 roku początkowo pracował jako kierowca ciężarówki, jednak szybko nawiązał kontakt z Russellem Bufalino, od którego stopniowo dostawał coraz więcej zleceń. Ich znajomość szybko przekształciła się w bliską przyjaźń, a Frank często przychodził do Russella po radę.
To również Russell Bufalino zapoznał Franka Sheerana z Jimmym Hoffą – przewodniczącym związku Teamsters (najpotężniejszego związku zawodowego kierowców ciężarówek i taksówek w tamtych latach w USA). Jimmy Hoffa był powszechnie znany ze swoich powiązań ze światem przestępczym, jednak przez długi czas nie można mu było niczego udowodnić. Niedługo po poznaniu Frank Sheeran i Jimmy Hoffa nawiązali przyjaźń. 30 lipca 1975 roku zaginął Jimmy Hoffa, który przybył do restauracji Manchus Red Fox, by spotkać się z przywódcą związkowym z Detroit, przedstawicielem Teamsters oraz przedstawicielem świata przestępczego. Ostatnim dowodem jego życia była rozmowa telefoniczna z żoną, której oznajmił, że spotkanie się przedłuża, ponieważ osoby z którymi miał się spotkać, spóźniają się. Przez długi czas nie można było ustalić przyczyny zaginięcia, aż do momentu w którym Frank Sheeran na chwilę przed śmiercią przyznał się do zabójstwa przyjaciela. Morderstwo zostało dokonane w domu, do którego przywieziono Jimmy’ego Hoffę na spotkanie.