A novel colorimetric method was developed for ultrasensitive detection of heparin based on self-assembly of gold nanoparticles (AuNPs) onto the surface of graphene oxide (GO). Polycationic protamine was used as a medium for inducing the self-assembly of citrate-capped AuNPs on GO through electrostatic interaction, resulting in a shift in the surface plasmon resonance (SPR) absorption of AuNPs and exhibiting a blue color. Addition of polyanionic heparin disturbed the self-assemble of AuNPs due to its strong affinity to protamine. With the increase of heparin concentration, the amounts of self-assembly AuNPs decreased and the color changed from blue to red in solution. Therefore, a "blue-to-red" colorimetric sensing strategy based on self-assembly of AuNPs could be established for heparin detection. Compared with the commonly reported aggregation-based methods ("red-to-blue"), the color change from blue to red was more eye-sensitive, especially in low concentration of target. Moreover, stronger interaction between protamine and heparin led to distinguish heparin from its analogues as well as various potentially coexistent physiological species. The strategy was simply achieved by the self-assembly nature of AuNPs and the application of two types of polyionic media, showing it to be label-free, simple, rapid and visual. This method could selectively detect heparin with a detection limit of 3.0 ng mL(-1) in standard aqueous solution and good linearity was obtained over the range 0.06-0.36 μg mL(-1) (R = 0.9936). It was successfully applied to determination of heparin in fetal bovine serum samples as low as 1.7 ng mL(-1) with a linear range of 0-0.8 μg mL(-1).