A method and apparatus of predictive Intra coding of a block are disclosed. In one embodiment according to the present invention, a same set of Intra prediction modes is used for PUs corresponding to different block sizes including a 4×4 block size and at least one other block size. In another embodiment of the present invention, the number of Intra prediction modes in the set is reduced by removing at least one Intra prediction mode from the set. For example, when the set of 35 Intra prediction modes is used, intraPredMode corresponding to 18, 34, or 26 can be removed. The current Intra prediction mode can be coded predictively based on said one or more neighboring PUs, wherein the current Intra prediction mode is predicted using 2 most probable modes (MPMs) and 32 remaining modes. The 32 remaining modes can be represented using 5-bit fixed length codes.