Graphene oxide (GO) has unique structural properties, can effectively adsorb single-strand DNA through π-π stacking, hydrogen bonding and hydrophobic interactions, and is useful in many biotechnology applications. In this study, we developed a thrombin-binding-aptamers (15- and 29-mer) conjugated graphene oxide (TBA15/TBA29-GO) composite for the efficient inhibition of thrombin activity towards the formation of fibrin from fibrinogen. The TBA15/TBA29-GO composite was simply obtained by the self-assembly of TBA15/TBA29 hybrids on GO. The high density and appropriate orientation of TBA15/TBA29 on the GO surface enabled TBA15/TBA29-GO to acquire an ultrastrong binding affinity for thrombin (dissociation constant = 2.9 × 10-12 M). Compared to bivalent TBA15h20A20/TBA29h20A20 hybrids, the TBA15/TBA29-GO composite exhibited a superior anticoagulant potency (ca. 10-fold) against thrombin-mediated coagulation as a result of steric blocking effects and a higher binding affinity for thrombin. In addition, the prolonged thrombin clotting time, prothrombin time (PT), and activated partial thromboplastin time (aPTT) of TBA15/TBA29-GO were at least 2 times longer than those of commercially available drugs (heparin, argatroban, hirudin, and warfarin). The in vitro cytotoxicity and hemolysis analyses revealed the high biocompatibility of TBA15/TBA29-GO. The rat-tail bleeding assay of the hemostasis time and ex vivo PT and aPTT further revealed that TBA15/TBA29-GO is superior (>2-fold) to heparin, which is commonly used in the treatment and prevention of thrombotic diseases. Our multivalent, oligonucleotide-modified GO nanocomposites are easy to prepare, cost-effective, and highly biocompatible and they show great potential as effective anticoagulants for the treatment of thrombotic disorders.