Shallow marine sandstones are substantial hydrocarbon reservoirs located around the globe and in Southeast Asia. Understanding the internal characteristics, distribution, geometry and lateral extent of these sandstones are essential parts of successful exploration and production strategy. This study presents the first detailed work on reservoir sandstone facies including textural characteristics of shallow marine sandstones (well-exposed outcrops) of the Nyalau Formation (Oligocene�Middle Miocene), Bintulu area, Sarawak, East Malaysia. This formation is the onshore equivalent of the offshore cycles II and III. We examined five different major types of sandstone facies on the basis of sedimentological characteristics, grain size distribution, porosity (�) and permeability (k). The analyzed sandstone facies are: (1) hummocky cross-stratified sandstones (� = 32.07 , k = 20.78 md; thickness from 1 to 2 m); (2) herringbone cross-bedded sandstones (� = 31.31 , k = 7.7 m; thickness from 1 to 10 m); (3) trough cross-bedded sandstones (� = 35.80 , k = 5.97 md; thickness from 0.5 to 1 m); (4) wavy- to flaser-bedded sandstones (� = 19.84 , k = 2.31 md; thickness from 0.5 to 3.5 m); and (5) bioturbated sandstones (� = 8.21 , k = 3.46 md; thickness from 1 to 2 m). By integrating these parameters, we observed that the best reservoir quality sandstones are hummocky cross-stratified sandstone and herringbone cross-bedded sandstone, because they have better porosity�permeability than that of other sandstone facies, despite having similar grain distribution with probability curves having steep trends and almost same grain size, roundness and sorting. Upon comparing the different facies, inferences can be made that porosity�permeability is distributed randomly. We conclude that there exist heterogeneities within different sandstone facies which may apply to the reservoir properties in the subsurface. © 2015, King Fahd University of Petroleum & Minerals.