In recent years, the synergistic effects of Au-based hybrids have generated enormous scientific interest. The hybrids of Au and Co are expected to exhibit attractive properties. In this paper, we report the successful fabrication of the nanohybrids between bulk-immiscible Au and Co with chain-like structures via a mild solution method. Elemental mapping, XRD and EXAFS data reveal that the as-prepared AuCo nanohybrids might be of cluster mixed configuration. A sequential redox and imperfection-promoted aggregation/diffusion process is proposed to elucidate the formation mechanism of the nanohybrids. The as-prepared products exhibit a temperature-independent saturation magnetization with the magnetic moment of Co as high as ~2.95 μ(B) for each Co atom at 300 K, much higher than the bulk value (~1.7 μ(B) for each Co atom) and approaching the theoretical value of an atomic Co (~3.0 μ(B) for each Co atom).