In a method of forming a gate structure, a gate pattern including a gate insulation layer pattern and a gate electrode sequentially stacked on a substrate is formed. The gate electrode includes a metal. A first plasma process is performed on the gate pattern using a reaction gas to reduce an oxidized edge portion of the gate electrode. The reaction gas includes nitrogen. A spacer is formed on a sidewall of the gate pattern. A threshold voltage is adjusted by reducing the oxidized edge portion of the gate electrode. Therefore, a semiconductor device including the gate pattern has excellent electrical characteristics.