When the regional power system is connected to main grid with the Voltage Source Converter based HVDC (VSC-HVDC), the main grid does not actively respond to frequency drop of the regional system; thus the regional system has less frequency control capability compared with that connected with AC line. Frequency control algorithm based on active power support from VSC-HVDC and adaptive under-frequency load shedding is proposed. With frequency drop in the regional system, the active power deficiency is estimated with the incremental method. With precondition of frequency security of the main grid, active power support is provided to the regional system by the VSC-HVDC. The adaptive under-frequency load shedding strategy is designed according to subsequent frequency drop. The numerical results show that the proposed algorithm effectively maintains frequency stability of the regional system and decreases load shedding.