An apparatus and method for setting up Quality of Service (QoS) in a wireless communication system are provided. The method includes, during an initial network entry, generating at least one static Service Flow (SF) by receiving a QoS profile from a Base Station (BS), if QoS change is requested for the SF, transmitting by a Mobile Station (MS) to the BS a service change request message which requests a service change and includes QoS change information, and by the BS, determining if the service change request is granted, and, if granted, transmitting a service change response message to the MS, and changing a QoS of the SF.