Le parc constitue la région la plus orientale de la Slovaquie et est parmi les plus faiblement peuplées du pays. La région appartient aux Carpates orientales externes et plus précisément au massif des Bukovské vrchy, appelé Bieszczady du côté polonais. Le plus haut sommet, qui culmine à , est le Kremenec et se trouve au tri-point entre la Slovaquie, la Pologne et l'Ukraine tandis que le point le plus bas, à , est la rivière Ulička lors de son entrée en Ukraine. La crête des Carpates, et donc les plus hauts sommets, se situe au niveau de la frontière entre la Pologne et la Slovaquie. Le sud du parc est aussi limité par une crête mais moins élevée et fendue par la vallée de la rivière Cirocha au nord du village de Stakčín ; cette entaille permettant, par ailleurs, le passage de la seule route d'accès au parc. Entre ces deux crêtes cinq vallées perpendiculaires à celles-ci et séparées, elles aussi, par de jolies lignes de crête.