Convenient and sensitive detection of tumor biomarkers is crucial for the early diagnosis and treatment of cancer. Herein, we present a probe-integrated and label-free electrochemical immunosensor based on binary nanocarbon composites and surface-immobilized methylene blue (MB) redox probes for detection of carbohydrate antigen 199 (CA19-9), which is closely associated with gastric malignancies. Nanocarbon composites consisting of electrochemically reduced graphene oxides and carbon nanotubes (ErGO-CNT) are electrodeposited onto an indium tin oxide (ITO) electrode surface to form a 3D nanocomposite film, which could provide high surface area to immobilize abundant MB probes, facilitate the electron transfer of MB, and therefore, improve sensitivity. Polydopamine (PDA) served as a bifunctional linker is able to immobilize anti-CA19-9 antibodies and stabilize the inner probe, conferring the sensing interface with specific recognition capacity. Electrochemical detection of CA19-9 is achieved based on the decrease of the redox signal of MB after specific binding of CA19-9 with a wide linear range of 0.1 mU/mL to 100 U/mL and a limit of detection (LOD) of 0.54 nU/mL (S/N = 3). The constructed electrochemical immunosensor has good selectivity, repeatability, reproducibility, and stability. Furthermore, determination of CA19-9 in human serum samples is also realized.