The study area, Madura Island separated from East Java by Madura Strait, is located in the North-East Java Basin. The early Middle Miocene Ngrayong Formation, an important petroleum reservoir, is well exposed in the central highland area of Madura. It is the product of a wide variety of depositional environments. The purpose of present study is to determine the reservoir quality based on the characteristics and geometry of sedimentary facies and the variation of depositional environments. The Ngrayong Formation in Madura Island can be identified into seven litho-facies and two facies associations. Cross-laminated sandstone facies (Smx) and heterolithic sandstone facies (Sm) are deposited in tide-dominated, littoral to sub-littoral environment. Dark grey siltstone facies (Fc), grey shale facies (Fs), laminated sandstone facies (Sl), fine grained sandstone facies (Sf) and bioclastic limestones facies (Lgb) are deposited in moderate-depth sub-littoral environment. In the study area, the depositional environment of Ngrayong Formation moves to deeper environment from north to south. The reservoir rocks deposited in upper neritic zone such as cross-laminated sandstones and heterolitic sandstones possess good reservoir quality. The reservoir rocks deposited in moderate-depth shallow marine shelf environment are also fair for reservoir potential. The cross-laminated sandstone (Smx) and heterolithic sandstone (Sm) in upper neritic sediments facies association and laminated sandstone (Sl) and fine grained sandstone (Sf) in lower neritic sediments facies association should be targeted for hydrocarbon exploration in Madura Island.