Methods and wireless communication devices for access procedure enhancement are provided. The wireless communication device for access procedure enhancement includes a transceiver module and a communication protocol module. The transceiver module performs wireless transmissions and receptions to and from a network. The communication protocol module divides an access channel into a plurality of narrow band frequency division multiplexing (FDM) channels, groups a plurality of reverse link FDM access channels (R-FACH) into a plurality of R-FACH groups, determines whether a base station in a network supports an access probe. If yes, the base station joins at least one R-FACH group. The wireless communication device sends the access probe in a chosen R-FACH during each access procedure.