Bells theorem shows a profound contradiction between local realism and quantum mechanics on the level of statistical predictions. It does not involve directly Einstein-Podolsky-Rosen (EPR) correlations. The paradox of Greenberger-Horne-Zeilinger (GHZ) disproves directly the concept of EPR elements of reality, based on the EPR correlations, in an all-versus-nothing way. A three-qubit experimental demonstration of the GHZ paradox was achieved nearly twenty years ago, and followed by demonstrations for more qubits. Still, the GHZ contradictions underlying the tests can be reduced to three-qubit one. We show an irreducible four-qubit GHZ paradox, and report its experimental demonstration. The reducibility loophole is closed. The bound of a three-setting per party Bell-GHZ inequality is violated by $7sigma$. The fidelity of the GHZ state was around $81%$, and an entanglement witness reveals a violation of the separability threshold by $19sigma$.