As graphene oxide-based oligonucleotide biosensors improve, there is a growing need to explore their ability to retain high sensitivity for low target concentrations in the context of biological fluids. Therefore, we innovatively combined assay milieu factors that could influence the key performance parameters of DNA hybridization and graphene oxide (GO) colloid dispersion, verifying their suitability to enhance oligonucleotide–GO interactions and biosensor performance. As a model system, we tested single-strand (ss) DNA detection in a complex solution containing bovine serum albumin (BSA) and salts with surfactants. A fluorescein conjugated 30-mer oligonucleotide ssDNA probe was combined with its complementary cDNA target, together with solute dispersed GO and either non-ionic (Triton X-100 and Tween-20) or anionic sodium dodecyl sulfate (SDS) surfactants. In this context, we compared the effect of divalent Mg2+ or monovalent Na+ salts on GO binding for the quench-based detection of specific target–probe DNA hybridization. GO biosensor strategies for quench-based DNA detection include a “turn on” enhancement of fluorescence upon target–probe interaction versus a “turn off” decreased fluorescence for the GO-bound probe. We found that the sensitive and specific detection of low concentrations of oligonucleotide target was best achieved using a strategy that involved target–probe DNA hybridization in the solution with a subsequent modified “turn-off” GO capture and the quenching of the unhybridized probe. Using carefully formulated assay procedures that prevented GO aggregation, the preferential binding and quenching of the unhybridized probe were both achieved using 0.1% BSA, 0.065% SDS and 6 mM NaCl. This resulted in the sensitive measurement of the specific target–probe complexes remaining in the solution. The fluorescein-conjugated single stranded probe (FAM–ssDNA) exhibited linearity to cDNA hybridization with concentrations in the range of 1–8 nM, with a limit of detection equivalent to 0.1 pmoles of target in 100 µL of assay mix. We highlight a general approach that may be adopted for oligonucleotide target detection within complex solutions.