Родился в Рио-де-Жанейро в благополучной семье инженера Педру и Лижии Коэльо. В семь лет он был отправлен в иезуитскую школу Святого Игнатия Лойолы, где впервые проявляется его желание писать книги. Желание стать писателем не нашло понимания у его семьи, поэтому под их давлением он поступает на юридический факультет университета Рио-де-Жанейро, но вскоре бросает учёбу и больше занимается журналистикой. В итоге разногласия между ним и семьёй шли по нарастающей, в конце концов семнадцатилетний Паулу был принудительно помещён в частную психиатрическую клинику для курса лечения. Ни лечение электрошоком из-за проявившейся шизофрении, ни второй курс лечения не изменили его уверенности в себе — и тогда он сбежал из клиники, скитался некоторое время, в итоге вернулся домой. Через год он примкнул к движению любительского театра, который в Бразилии 60-х годов стал массовым явлением — не только явлением искусства, но и социального протеста. Театрально-протестная активность для Коэльо закончилась в лечебнице, откуда он снова сбежал, но безденежье вынудило его вновь вернуться домой. В итоге после третьего курса лечения его семья смирилась с тем, что «нормальной» работой он заниматься не будет. Пауло Коэльо продолжал заниматься театром и журналистикой.
В 1970 начал путешествовать по Мексике, Перу, Боливии, Чили, Европе и Северной Африке. Через два года Коэлью вернулся в Бразилию и начал сочинять стихи для песен, ставших потом очень популярными, работая с известными бразильскими исполнителями, такими как Рауль Сейшас. Как он признаётся в одном из интервью, в это время он познакомился с работами противоречивого английского мистика, Алистера Кроули, повлиявшими на его творчество. Оно распространилось не только на музыку, но и на планы создания «Альтернативного общества», которое должно было стать общиной анархистов в штате Минас-Жерайс, основанной на идее Кроули: «Делай что хочешь — таков весь закон». Бразильские военные, пришедшие к власти в результате переворота 1964 года, посчитали этот проект подрывной деятельностью и заключили всех предполагаемых членов группы под стражу. Известно также, что во время пребывания в тюрьме Коэльо, его жену и Рауля Сейшаса пытали. Выйти из тюрьмы Коэльо неожиданно помогло прошлое: его признали невменяемым и отпустили.
Позднее, во время путешествия со своей нынешней четвёртой женой Кристиной, в Голландии, он встречает личность (называемую им «Джей» (лат. J) в «Валькириях», «Паломничестве» и на его сайте «Воин Света»), которая изменила его жизнь и посвятила в христианство. Он стал членом католической группы, известной как RAM (Regnus Agnus Mundi), где «Джей» был его «Учителем». В 1986 году он прошёл Дорогой Сантьяго, старинным испанским путём паломников, и описал позднее всё произошедшее в книге «Дневник Мага». В 1988 году, сразу после выхода книги Алхимик «Джей» отправляет Пауло вместе с женой Кристиной в паломничество на 40 дней в пустыню Мохаве в Соединённых Штатах Америки. Позднее эти события Пауло описывает в книге Валькирии.
Сейчас он живёт со своей женой Кристиной, в Рио-де-Жанейро, в Бразилии, и в Тарбе, во Франции.
В 150 странах мира было продано более 86 миллионов книг Пауло Коэльо, переведённых на 67 языков. Он получил множество литературных премий в разных странах, включая Францию (La Legion d’Honneur) и Италию (Grinzane Cavour). Список его романов включает «Алхимика», основанного на «Истории о двух мечтателях» Борхеса, и проданного общим тиражом более 11 миллионов экземпляров, переведённых на 41 язык мира, положившего начало фильму, снимаемому Лоуренсом Фишборном, поклонником Коэльо. Кроме того, им написано «Паломничество» (лёгшее в основу компьютерной игры, разработанной компанией Arxel Tribe), «На берегу Рио-Пьедра села я и заплакала…» и «Валькирии». Его новелла «Заир», изданная в 2005 году, была запрещена в Иране с конфискацией 1000 копий, впоследствии всё-таки допущенных к печати.
Его произведения входили в список самых продаваемых книг не только в Бразилии, но и в Великобритании, США, Франции, Германии, Канаде, Италии, Израиле, Финляндии и Греции. «Алхимик» до сих пор остаётся самой продаваемой книгой в истории Бразилии и упомянут в Книге рекордов Гиннесса. Коэльо является автором самых продаваемых книг на португальском языке.
Несмотря на весь этот успех, многие бразильские критики считают его незначительным писателем, чьи работы слишком просты. Некоторые из них также называют его работы «коммерческими» и ориентированными на рынок. Его избрание в Литературную академию Бразилии оспаривается многими бразильцами. Известная российская телеведущая и сценарист Авдотья Смирнова сказала о нём следующее:
Российский писатель Баян Ширянов (Кирилл Воробьёв) высказал мысль, что популярность книг вроде «Алхимика» можно объяснить исключительно конъюнктурой. По мнению Ширянова, «Алхимик» — «это растянутая на двести страниц маленькая ветхозаветная притча, в оригинале состоящая из двух абзацев».
Стилизации в духе Коэлью присутствуют в книгах Анхеля де Куатьэ.
В январе 2011 года правительство Ирана запретило печатать и продавать любые книги Пауло Коэльо. Никаких объяснений по этому поводу власти Ирана не дали.