Cell-free DNA (cfDNA) circulates in the bloodstream packed in membrane-coated structures (such as apoptotic bodies) or bound to proteins. To identify proteins involved in the formation of deoxyribonucleoprotein complexes circulating in the blood, native complexes were isolated using affinity chromatography with immobilized polyclonal anti-histone antibodies from plasma of healthy females (HFs) and breast cancer patients (BCPs). It was found that the nucleoprotein complexes (NPCs) from HF plasma samples contained shorter DNA fragments (~180 bp) than BCP NPCs. However, the share of DNA in the NPCs from cfDNA in blood plasma in HFs and BCPs did not differ significantly, as well as the share of NPC protein from blood plasma total protein. Proteins were separated by SDS-PAGE and identified by MALDI-TOF mass spectrometry. Bioinformatic analysis showed that in the presence of a malignant tumor, the proportion of proteins involved in ion channels, protein binding, transport, and signal transduction increased in the composition of blood-circulating NPCs. Moreover, 58 (35%) proteins are differentially expressed in a number of malignant neoplasms in the NPCs of BCPs. Identified NPC proteins from BCP blood can be recommended for further testing as breast cancer diagnostic/prognostic biomarkers or as being useful in developing gene-targeted therapy approaches.