Rođen je 1. prosinca 1946. u Širokom Brijegu. Odmah po punoljetnosti napušta tadašnju Jugoslaviju i odlazi u Njemačku. Pridružuje se emigrantskoj organizaciji Ujedinjeni Hrvati Njemačke.Otvara vlastitu kockarnicu u Singenu na Bodenskom jezeru. Surađivao je navodno s njemačkom tajnom službom BND i službama nekih drugih europskih zemalja.
Početkom devedesetih na početku srpske agresije dolazi u Hrvatsku. Osniva Kažnjeničku bojnu, s kojom po izbijanju rata 1992. prelazi u BiH. Sjedište joj je bilo u Širokom Brijegu. Čine ju dragovoljci iz raznih zemalja, pa i oni za kojima su bile raspisane tjeralice Interpola. Skupina pripadnika te postrojbe navodno je sudjelovala u likvidaciji čelnika HOS-a Blaža Kraljevića i osmorice njegovih suboraca 9. kolovoza 1992. u Kruševu kod Mostara. Prema službenoj verziji, pripadnici HOS-a zapucali su na kontrolnu točku nakon čega su Kraljević i pratnja likvidirani. Istraga o tome nikada nije dovršena.
Kažnjenička bojna potom sudjeluje u sukobima s Bošnjacima kod Jablanice, u Mostaru i u drugim mjestima. U prosincu 1993. uključena je u sastav 2. Gardijske brigade HVO-a. Njihov zapovjednik Mladen Naletilić Tuta, međutim, ulazi u sukobe i s visokim dužnosnicima HVO-a. Tako se Tuta sukobio u studenom 1993. s generalom Slobodanom Praljkom. Zbog samovolje koju je provodio, umalo dolazi i do međumjesnih sukoba u Hercegovini.
Skupina pripadnika te bojne na silu je u prosincu 1993. upala u zatvor u Ljubuškom i, prethodno razoružavši stražare, otela vojnika HVO-a Roberta Nosića koji je u jednoj svađi ranio jednog pripadnika Kažnjeničke bojne. Nosiću se od tada gubi svaki trag.
Zbog svoje djelanosti na granici ili izvan zakona Tuta postaje sve veći problem i vlastima u Hrvatskoj. Sukobljava se i s čelnikom HIS-a Miroslavom Tuđmanom koji o njemu 1996. sastavlja izvješće upućeno predsjedniku Franji Tuđmanu i ministru obrane Gojku Šušku u kojemu tvrdi da Tuta nije nikakav politički emigrant, kako se predstavljao u javnosti, nego osoba sklona kriminalu i pripadnik podzemlja.
Kako je ranije već bila podignuta optužnica protiv njega zbog otmice Roberta Nosića, hrvatska policija uhitila ga je u veljači 1997. kada je s nekoliko prijatelja prešao u Hrvatsku. Uhićenje su proveli pripadnici protuteritorstičke postrojbe Lučko. Proveo je dvije godine u zatvoru u Remetincu, a kako je 1998. protiv njega podignuta i haaška optužnica, izručen je u Haag u ožujku 2000. godine. U tamošnjem pritvoru bio je jedan od aktivnijih pritvorenika. Bavio se sportom, redovito je igrao odbojku, družio se sa Slobodanom Miloševićem a mediji su donosili i izvješća kako je redovito igrao šah s Vojislavom Šešeljom.
Osuđen je na 20 godina zatvora zbog etničkog čišćenja Bošnjaka na području Mostara i Jablanice, te je nakon izdržane dvije trećine kazne od 20 godina u veljači 2013. pušten na slobodu. Većinu kazne proveo je u haaškom pritvoru dok je zadnjih pet godina bio u zatvoru Rebibbia u Rimu. Odmah nakon dolaska u Hrvatsku, pokrenut je sudski proces u kojem ga se tereti za ubojstvo Roberta Nosića. Proces vodi sudac Ivan Turudić.
Mladen Naletilić Tuta trenutno živi u Zagrebu gdje se redovito pojavljuje na sudskom procesu. Iznad Širkog Brijega, na Ciganskom brdu, sagradio je kuću u kojoj je živio s obitelji, suprugom i dva sina. Kuća je sada prazna. Žive u Zagrebu.