The invention provides a method of forming a semiconductor device and its gate structure, comprising methods of patterning metal gate structures including a high-k gate dielectric. In an embodiment, a soluble hard mask layer may be used to provide a masking element to pattern a metal gate. The soluble hard mask layer may be removed from the substrate by water or a photoresist developer. In an embodiment, a hard mask including a high-k dielectric is formed. In a further embodiment, a protection layer is formed underlying a photoresist pattern. The protection layer may protect one or more layers formed on the substrate from a photoresist stripping process. Compared with the prior technology, the method may provide improved adhesion of the photoresist layer. Further advantages may be seen byreduction of damage to the high-k gate dielectric and/or metal gate that may be caused by conventional dry ash and/or wet etch removal of a photoresist layer and/or hard mask.