This paper addresses the problem of determining the stability gain space of a PID controller for general second-order time-delay systems. First, a review of existing results and the associated drawbacks is presented. Subsequently, a new algorithm to compute the entire PID stability gain space is developed. The new algorithm is based upon existing results on the relationship between the stability of a quasi-polynomial and its derivatives, an extended version of the Hermit-Biehler theorem, and also the Nyquist criterion. The algorithm entails extraction of an admissible range for the PID parameter K-p, and then based on this range, a stability region in the (K-i -K-d) plane is computed. Well-known examples are studied to demonstrate the reliability and accuracy of the results.