Upregulation of the chemokine receptor CXCR4 contributes to the progression and metastasis of both solid and hematological malignancies, rendering this receptor an attractive therapeutic target. Besides the only FDA-approved CXCR4 antagonist Plerixafor (AMD3100), multiple other classes of CXCR4-targeting molecules are under (pre-)clinical development. Nanobodies (Nb), small single variable domains of heavy-chain only antibodies from Camelids, have appeared to be ideal antibody-fragments for targeting a broad range of epitopes and cavities within GPCRs such as CXCR4. Compared to conventional antibodies, monovalent nanobodies show fast blood clearance and no effector functions. In order to further increase their binding affinities and to restore antibody-mediated effector functions, we have constructed three different bivalent nanobody Fc-fusion molecules (Nb-Fc), targeting distinct epitopes on CXCR4, via fusion of Nbs to a Fc domain of a human IgG1 antibody. Most Nb-Fc constructs show increased binding affinity and enhanced potency in CXCL12 displacement, inhibition of CXCL12-induced signaling and CXCR4-mediated HIV entry, when compared to their monovalent Nb counterparts. Moreover, Nb-Fc induced ADCC- and CDC-mediated cell-death of CXCR4-overexpressing CCRF-CEM leukemia cells and did not affect cells expressing low levels or no CXCR4. These highly potent CXCR4 Nb-Fc constructs with Fc-mediated effector functions are attractive molecules to therapeutically target CXCR4-overexpressing tumors.