Предки Пауло Аутуори были итальянцами. По окончании школы серьёзно занялся высшим образованием, связанным со спортом. У него имеется образование в области физического воспитания (Университет Каштелу-Бранку в Рио), управления в спорте (Католический Университет Рио-де-Жанейро), а также успешно окончены курсы футбольного тренера в Университете штата Рио-де-Жанейро.
С 1974 по 1985 год работал с довольно скромными командами штатов Рио и Сан-Паулу, в которых набирался тренерского опыта. В 1986 году впервые принял один из великих клубов Рио — «Ботафого». Этот клуб с 1968 (вскоре после ухода Гарринчи) по 1989 год не выиграл ни одного трофея, и в свой первый приход в команду «Одинокой звезды» и Аутуори не удалось завоевать титулов. Довольно скоро Пауло принял решение отправиться в Португалию, где у него было достаточно возможностей для тренерских манёвров со скромными, но крепкими командами типа «Витории» из Гимарайнша, «Насьонала» и «Маритиму».
В дальнейшем, в периоды работы у себя на родине, возглавлял исключительно великие бразильские клубы, входящие в число основателей Клуба Тринадцати.
В 1995 году Аутуори добился своего первого серьёзного успеха. Возглавляемый им «Ботафого» впервые в своей истории выиграл чемпионат Бразилии. В команде, проведшей великолепный сезон, лидерами были Гонсалвес, Донизете и Тулио Маравилья, который был поистине идолом торсиды «Ботафого» (они называют этот период «Тулиоманией»).
После триумфа с «Ботафого» Пауло Аутуори возглавил другой великий клуб — на сей раз европейскую команду «Бенфику», которая в 1990-е годы ушла в тень блиставшего тогда «Порту». С «Орлами» Аутуори занял третье место в чемпионате Португалии, после чего вернулся в Бразилию.
Грандиозным для Аутуори стал 1997 год — вначале была добыта победа в Лиге Минейро, а затем — в Кубке Либертадорес, ставшим для «Крузейро» вторым в истории клуба. В 1998—2000 годах произошла некоторая стагнация в результатах Аутуори — несмотря на то, что Пауло возглавлял такие клубы, как «Фламенго», «Интернасьонал», «Сантос», «Ботафого», «Крузейро», нигде он не задерживался дольше года.
2001—2005 годы в биографии тренера можно назвать «перуанским периодом». Он дважды становился чемпионом Перу, причём с разными командами — вначале с «Альянсой Лима» (2001), а затем (после краткосрочного возвращения в «Ботафого») — со «Спортинг Кристал» (2002). Отметив высокие результаты с клубами, Федерация Футбола Перу попросила Аутуори возглавить национальную сборную этой страны. На домашнем Кубке Америки 2004 года перуанцы вышли в 1/4 финала, однако жестокий жребий свёл их с великолепной аргентинской командой, которой в итоге не хватило нескольких минут до своего пятнадцатого титула чемпионов Америки. Хозяева уступили с минимальным счётом, а работа Аутуори была расценена как успешная.
В апреле 2005 года Аутуори возглавил «Сан-Паулу», сменив Эмерсона Леао, и провёл фантастический сезон с «Трёхцветными Паулисты». Кампания в Кубке Либертадорес 2005 увенчалась уверенной победой по сумме двух встреч над «Атлетико Паранаэнсе» в первом в истории чисто бразильском финале. В декабре «Сан-Паулу», трёхкратный чемпион Южной Америки, в третий раз в своей истории официально стал и лучшим клубом планеты — в финале клубного чемпионата мира «паулистас» обыграли английский «Ливерпуль» за счёт единственного гола Минейро. 29 декабря 2005 года покинул «Сан-Паулу».
В дальнейшем работал в клубах Японии («Касима Антлерс») и Катара («Аль-Райян»), перемежая эти периоды с не слишком успешными возвращениями в Бразилию («Крузейро», «Гремио»).