W 1960 został dopuszczony do wykonywania zawodu adwokata zarówno w stanie Maine, jak i w Waszyngtonie.
W latach 1960–1962 pracował jako prawnik procesowy w wydziale antymonopolowym Departamentu Sprawiedliwości. Następnie (1962–1965) był asystentem senatora Edmunda Muskiego. Po zakończeniu pracy u niego prowadził własną praktykę w Portland (Maine, 1965–1977). Prócz tego w 1971 był asystentem prokuratora Cumberland County.
Wczesna kariera publiczna W 1974 zdobył nominację demokratów z Maine jako kandydat na gubernatora, pokonując w prawyborach Josepha Brennana, który później sam zdobył to stanowisko. Mitchell przegrał, podobnie jak kandydat Partii Republikańskiej, z niezależnym kandydatem .
Jego kariera nie uległa jednak załamaniu, gdyż w 1977 prezydent Jimmy Carter mianował go prokuratorem federalnym na Maine. Pełnił tę funkcję do 1979, kiedy mianowano go z kolei sędzią sądu federalnego.
Senator Po rezygnacji z mandatu Muskiego, który został sekretarzem stanu, dawny oponent Mitchella, gubernator Brennan, mianował go senatorem w celu zapełnienia wakatu. Mitchell po dokończeniu kadencji Muskiego był wybierany dwukrotnie na własne sześcioletnie kadencję: w 1982 i 1988.