A method and apparatus for Intra prediction mode encoding or decoding based on multi-level most probable modes (MPMs) are disclosed. In one embodiment according to the present invention, the method and apparatus for encoding or decoding Intra prediction mode for 4×4 prediction unit (PU) use 19 Intra mode candidates to have full directional coverage or 35 Intra mode candidates as used by 8×8, 16×16 and 32×32 PUs. In another embodiment of the present invention, three MPMs are used to code the Intra modes. Various methods to derive the three MPMs based on the Intra modes of neighboring blocks are disclosed. In yet another embodiment of the present invention, the coding method for the remaining modes comprises fixed length coding. In addition, variable length coding for the remaining modes are also disclosed.