An apparatus and method for video coding based on flexible slice structure are disclosed. In the recent high efficiency video coding (HEVC) development, the slice may contain multiple LCUs instead of macroblocks. The LCU size being considered is 64×64 pixels which is much larger than the macroblock size of 16×16 pixels. Compared with the macroblock aligned slice for H.264, the LCU-aligned slice for HEVC does not provide enough granularities for dividing video frames. Consequently, a flexible slice structure is developed where slice partition is based on smaller coding units. In the flexible slice structure, the first LCU and the last LCU of the slice are allowed to be a fractional LCU, which is derived from a whole LCU using quadtree partition. Syntax elements are also developed to enable conveyance of flexible slice structure between an encoder and a decoder efficiently.