W 1956 zarzucono mu defraudację pokaźnej sumy z funduszu reprezentacyjnego ESSO (sam mówi, iż „w większości były to niewinne kaprysy związane z promocją kultury”Biograficzny film dokumentalny Infierno Inolvidable, reż. Luis Alfredo Sánchez, Kolumbia-Francia-Meksyk, 1995.) i postawiony w stan oskarżenia zdecydował się wyemigrować wpierw do Europy, a następnie do Meksyku, gdzie koncern ESSO nie miał wstępu z uwagi na nacjonalizację przemysłu naftowego przeprowadzoną w latach 40. przez rząd Cardenasa.
W Meksyku prędko znalazł pracę w branży reklamowej i telewizji, np. użyczył swojego głosu do dubbingu znanego amerykańskiego serialu Nietykalni. Natomiast jego artystyczne zainteresowania zjednały mu wielu przyjaciół w środowisku literatów i filmowców, takich jak Octavio Paz, Juan José Arreola, Carlos Fuentes, Elena Poniatowska i Luis Buñuel.
W 1959 w wyniku uznania roszczeń koncernu naftowego ESSO Mutis został skazany i osadzony na 15 miesięcy w więzieniu prewencyjnym Lecumberri. Było to dla niego wydarzenie decydujące nie tylko z życiowego punktu widzenia, ale i w kontekście dalszej drogi artystycznej. W więzieniu napisał swoją pierwszą powieść Diario de Lecumberri, która przyniosła mu rozgłos i została opublikowana w Meksyku jeszcze w 1960.