The power system continuously deals with frequency fluctuations. When a power disturbance occurs, the transmission system operators rely on the underfrequency load shedding (UFLS) scheme to address severe underfrequency (UF) events to maintain the frequency at the permissible level and prevent blackouts. Defining settings of a conventional UFLS scheme is a very complex problem due to the nonlinear nature of the frequency response, and the size of the problem is vast because of the number of UF-relays spread on the power system. The under or over total load disconnection produced by the wrong setting of the UF-relays can create secondary frequency events or even a total blackout. This paper introduces a novel method to compute an optimally parametrized conventional UFLS scheme in specific given operating conditions by formulating it as a constrained problem and using the Improved Harmony Search (IHS) algorithm to solve it. Since there is no previous knowledge of using IHS to solve the UFLS scheme, a numerical parameter sensitivity analysis (PSA) is developed to tune the parameter of the IHS algorithm. The IEEE 39-bus system was modelled in DIgSILENT® PowerFactory™ and used as a test system. The optimally parametrized conventional UFLS methodology presented in this paper reveals superior results against the conventional UFLS scheme, and the suitability of using the IHS algorithm is confirmed.