This paper proposes a novel distributed coordination load shedding (DCLS) approach for an islanded microgrid (MG) using sub-gradient algorithm of multi-agent system. The main objective is to achieve practical and optimal LS and obtain an optimum amount of load to be shed in a fully distributed manner under large disturbances. To coordinate the controllable loads (CLs) in an MG, an LS level (LSL) is first defined and evaluated locally to take the CL capacity and the LS willingness into consideration. Then, by updating the LSLs and the local frequency deviation measured based on frequency-inertia dynamics response, the proposed DCLS can be accomplished based on the sub-gradient algorithm. More importantly, only local information is needed to be updated during the entire DCLS process. Hence, the power supply demand balance can be well maintained, the utilization of LS can be significantly improved, and the requirements for communication topology changes can be adaptively met in a fully distributed way. The simulation results indicate that the proposed sub-gradient-based distributed coordination algorithm and corresponding DCLS are effective and adaptive.