The Sandakan Formation of the Segama Group is exposed across the Sandakan Peninsular in eastern Sabah. This Upper Miocene part of the Segama Group unconformably overlies the Garinono Formation and is conformably overlain by the Bongaya Formation. This formation was investigated with detailed logging of outcrops and microfossils analysis in order to map the depositional facies and sedimentary environment. This study showed the presence of seven lithofacies: Thick amalgamated sandstone; thin, lenticular interbedded HCS sandstones and mudstone; laminated mudstone with Rhizophora; trough cross-bedded sandstone; laminated mudstone; strip mudstone with thin sandstone and siltstone; and interbedded HCS sandstone and mudstone. Based on the presence of Rhizophora, Brownlowia, Florchuetia sp., Polypodium, Stenochleana palustris, Ascidian spicule low angle cross bedding, very fine grained sandstone, thin alternations of very fine sandstone, silt and clay layers showing cyclicity (muddy rhythemites), rocks in the Sandakan Formation are interpreted as mangal estuary and open marine facies. Three facies associations could be deduced from the seven lithofacies: Gradual coarsening upwards shoreface; abrupt change facies and prograding estuary facies association.