Pierwszym wyborem do zagrania roli czarnego charakteru był Jack Nicholson. O angaż starał się także Bill Goldberg. Na pewnym etapie produkcji chęć powrotu do serii wyraził Jean-Claude Van Damme, który miał pomysł, by wcielić się w brata bliźniaka postaci z drugiej części filmu.
Projekt pierwotnie miał być spin-offem serii "Niezniszczalnych" i skupiać się na postaci granego przez Jasona Stathama Lee Christmasa. Tytułem roboczym przez długi czas był "A Christmas Story". Stanowisko reżysera negocjowali Duncan Jones oraz D.J. Caruso. Perturbacje produkcyjne oraz zmiany kierunku wizji sprawiły, że projekt z powrotem przemianowano na czwartą część "Niezniszczalnych".
Zdjęcia do filmu kręcono w Salonikach (Grecja), Sofii (Bułgaria) oraz Londynie (Anglia, Wielka Brytania).