This study analyses the rhodolith-bearing deposits in the largest and most rhodolith-rich outcrop of the Polish Outer Carpathian flysch, located in the Silesian Nappe, at the village of Melsztyn. The rhodoliths and sparse associated biota occur as resedimented components in a deep-marine succession of siliciclastic conglomerates and coarse-grained sandstones, deposited by high-density turbidity currents and debris flows. The sediment was derived from a fan-delta system located at the southern margin of the Silesian flysch basin. Stratigraphic data indicate that the succession represents the Upper Istebna Sandstone deposited during the Late Paleocene. The rhodoliths are composed mostly of coralline red algae with seven genera and eight species representing the family Sporolithaceae and the subfamilies Mastophoroideae and Melobesioideae. Rhodoliths show sub-spheroidal and sub-ellipsoidal shapes with encrusting, warty and lumpy growth forms. Lumpy growth forms show massive inner arrangements, whereas the encrusting growth forms are usually made of thin thalli and show more loosely packed inner arrangements. The rhodoliths grew on a moderately mobile siliciclastic substrate in a shallow-marine environment with a low net sedimentation rate. It is inferred that the growth of rhodoliths was favored during a relative sea-level rise. During the subsequent sea-level fall, the rhodoliths and associated siliciclastic deposits were resedimented by gravity flows into the deep-sea setting. The analyzed deposits, like other Paleocene–Eocene deposits of the Polish Outer Carpathians, provide no evidence of coeval widespread shallow-marine carbonate sedimentation along the margins of the Outer Carpathian flysch basins.