Methods, apparatuses and systems directed to an automatic network traffic discovery and classification mechanism that includes dynamically adjusted traffic discovery thresholds. In one implementation, the dynamic discovery thresholds are adjusted based on analysis of one or more operational parameters associated with network traffic discovery, and/or network traffic characteristics. The present invention in one implementation can be configured to dynamically adjust one or more thresholds or range limits that affect the behavior of the automatic traffic classification mechanism, such as the rate at which new traffic classes are added to a traffic classification database. One implementation of the present invention minimizes the user intervention often required with the use of static traffic discovery thresholds.