Provided is a method of forming a contact structure. The method includes forming a conductive pattern on a substrate. An interlayer insulating layer covering the conductive pattern is formed. The interlayer insulating layer is patterned to form an opening partially exposing the conductive pattern. An oxide layer is formed on substantially the entire surface of the substrate on which the opening is formed. A reduction process is performed to reduce the oxide layer. Here, the oxide layer on a bottom region of the opening is reduced to a catalyst layer, and the oxide layer on a region other than the bottom region of the opening is reduced to a non-catalyst layer. A nano material is grown from the catalyst layer, so that a contact plug is formed in the opening.