This series of two papers is devoted to the effect of organic dye (methylene blue, MB; or methyl orange, MO) adsorption on the surface of either bare or citrate-coated magnetic iron oxide nanoparticles (IONPs) on their primary agglomeration (in the absence of an applied magnetic field) and secondary field-induced agglomeration. The present paper (Part I) is focused on physicochemical mechanisms of dye adsorption and adsorption-induced primary agglomeration of IONPs. Dye adsorption to oppositely charged IONPs is found to be mostly promoted by electrostatic interactions and is very sensitive to pH and ionic strength variations. The shape of adsorption isotherms is correctly reproduced by the Langmuir law. For the particular MB/citrated IONP pair, the maximum surface density of adsorbed MB seems to correspond to the packing density of an adsorbed monolayer rather than to the surface density of the available adsorption sites. MB is shown to form H-aggregates on the surface of citrate-coated IONPs. The effective electric charge on the IONP surface remains nearly constant in a broad range of surface coverages by MB due to the combined action of counterion exchange and counterion condensation. Primary agglomeration of IONPs (revealed by an exponential increase of hydrodynamic size with surface coverage by MB) probably comes from correlation attractions or π-stacking aromatic interactions between adsorbed MB molecules or H-aggregates. From the application perspective, the maximum adsorption capacity is 139 ± 4 mg/g for the MB/citrated IONP pair (pH = 4–11) and 257 ± 16 mg/g for the MO/bare IONP pair (pH ∼ 4). Citrated IONPs have shown a good potential for their reusability in water treatment, with the adsorption efficiency remaining about 99% after nine adsorption/desorption cycles.