Understanding crystal growth and improving material quality is important for improving semiconductors for electronic, optoelectronic, and photovoltaic applications. Amidst the surging interest in solar cells based on hybrid organic-inorganic lead halide perovskites and the exciting progress in device performance, improved understanding and better control of the crystal growth of these perovskites could further boost their optoelectronic and photovoltaic performance. Here, we report new insights on the crystal growth of the perovskite materials, especially crystalline nanostructures. Specifically, single crystal nanowires, nanorods, and nanoplates of methylammonium lead halide perovskites (CH3NH3PbI3 and CH3NH3PbBr3) are successfully grown via a dissolution-recrystallization pathway in a solution synthesis from lead iodide (or lead acetate) films coated on substrates. These single crystal nanostructures display strong room-temperature photoluminescence and long carrier lifetime. We also report that a solid-liquid interfacial conversion reaction can create a highly crystalline, nanostructured MAPbI3 film with micrometer grain size and high surface coverage that enables photovoltaic devices with a power conversion efficiency of 10.6%. These results suggest that single-crystal perovskite nanostructures provide improved photophysical properties that are important for fundamental studies and future applications in nanoscale optoelectronic and photonic devices.