Paweł Nastula tiene seis derrotas contra seis oponentes en su carrera de MMA. Para una lista de las mejores peleas de Nastula, consulta "Mejores peleas de Paweł Nastula".
El 6 de diciembre de 2014 Paweł Nastula se enfrentó a Mariusz Pudzianowski en un combate de completo a la edad de 44. Él entró con un récord de 5-6 (5), y Pudzianowski tenía 37 años y un récord de 7-3 (4). Nastula perdió la pelea por asalto 3º decisión unánime.
El 28 de septiembre de 2013 Paweł Nastula se enfrentó a Karol Bedorf en un combate de completo titulado por el título KSW Championship. Nastula tenía 43 años y un récord de 5-5 (5). Nastula perdió la pelea por asalto 2º TKO.
El 24 de agosto de 2008 Paweł Nastula se enfrentó a Yang Dongi a la edad de 38. Él entró con un récord de 1-4 (1), y Dongi tenía 23 años y un récord de 6-0 (6). Nastula perdió la pelea por TKO en el asalto 2º.
El 21 de octubre de 2006 Paweł Nastula se enfrentó a Josh Barnett a la edad de 36. Él entró con un récord de 1-3 (1), y Barnett tenía 28 años y un récord de 22-4 (18). Nastula perdió la pelea por sumisión en el asalto 2º.
El 31 de diciembre de 2005 Paweł Nastula se enfrentó a Alexander Emelianenko a la edad de 35. Él entró con un récord de 0-2 (0), y Emelianenko tenía 24 años y un récord de 7-1 (5). Nastula perdió la pelea por sumisión en el asalto 1º.
El 26 de junio de 2005 Paweł Nastula se enfrentó a Antônio Rodrigo Nogueira a la edad de 35. Él entró con un récord de 0-1 (0), y Nogueira tenía 29 años y un récord de 24-3-1 (15). Nastula perdió la pelea por TKO en el asalto 1º.
