InAs quantum dots (QDs) are grown epitaxially on Au-catalyst-grown GaAs nanowires (NWs) by metal organic chemical vapor deposition (MOCVD). These QDs are about 10-30 nm in diameter and several nanometers high, formed on the {112} side facets of the GaAs NWs. The QDs are very dense at the base of the NW and gradually sparser toward the top until disappearing at a distance of about 2 μm from the base. It can be concluded that these QDs are formed by adatom diffusion from the substrate as well as the sidewalls of the NWs. The critical diameter of the GaAs NW that is enough to form InAs QDs is between 120 and 160 nm according to incomplete statistics. We also find that these QDs exhibit zinc blende (ZB) structure that is consistent with that of the GaAs NW and their edges are faceted along particular surfaces. This hybrid structure may pave the way for the development of future nanowire-based optoelectronic devices.