Absolwent krakowskiej Akademii Sztuk Pięknych, autor polichromii Nowe Jeruzalem w kościele św. Klemensa w Trzemeśni oraz polichromii Bracia franciszkanie w bernardyńskim refektarzu w Krakowie. Autor witraży do kaplicy w Porębie.
Ilustracje tego autora znajdują się w wielu elementarzach oraz podręcznikach, a także w edycjach klasyki literatury, książkach religijnych i wielu innych. Znajdują się między innymi w książkach dla młodych czytelników: Przygody Tomka Sawyera (w tłum. Pawła Łopatki, 2004) oraz Książę i żebrak i Przygody Hucka (obie w tłum. Marcela Tarnowskiego, 2005) Marka Twaina, wiersze Juliana Tuwima Cuda i dziwy (2001), Przygody Scyzoryka Hanny Ożogowskiej (2002), Pollyanna Eleanor H. Porter (2004), Wyspa skarbów Roberta Louisa Stevensona (w tłum. Michała Filipczuka, 2005). Tworzył także ilustracje do współczesnych publikacji, takich jak: Modlitwa Celtów (2002) oraz Krzyż Celtów. Misterium i poezja w wyborze (2008) w wyborze Aliny Krajewskiej, Symbolika stroju subkultur i ruchów kontrkulturowych w okresie PRL Kingi Trojanowskiej (2024), Ten dzielny Miś. Wojenne przygody pluszowego niedźwiadka Bohdana Królikowskiego (2023), Ilustrowany słownik niemiecko-polski, polsko-niemiecki Adriana Golisa (2022), Chmura do picia Aliny Dudy (2022), Cudowny medalik. Opowieść o świętej Katarzynie Labouré (2009) oraz Św. Katarzyna ze Sieny. Dziewczynka, która widziała świętych na niebie (2021) Mary Fabyan Windeatt.
Jego ilustratorska twórczość skupia się na ukazywaniu kluczowych wydarzeń dziejowych, przedstawianiu polskich władców, bohaterów narodowych i religijnych, dzięki czemu stanowi dla czytelnika ciekawą podróż przez historię. Z kolei graficzna powieść Apokalipsa świętego Jana… łączy tekst biblijny z sugestywną formą graficzną. Dzięki graficznej formie czytelnik może lepiej zgłębić sugestywną wizję św. Jana. Książka ta zachęca do medytacji, modlitwy i głębszego zrozumienia tekstu biblijnego. Dodatkowym atutem takiej formy są rysunki – pełne detali i emocji, sprawiają bowiem, że lektura staje się nie tylko duchowym, ale i estetycznym doświadczeniem.
Więcej na temat twórczości Pawła Kołodziejskiego znaleźć można na jego stronie internetowej www.kolodziejskiart.pl