It has been conjectured that counterfactual communication is impossible, even for post-selected quantum particles. We strongly challenge this by proposing precisely such a counterfactual scheme where -- unambiguously -- none of Alice's photons that correctly contribute to her information about Bob's message have been to Bob. We demonstrate counterfactuality experimentally by means of weak measurements, and conceptually using consistent histories -- thus simultaneously satisfying both criteria without loopholes. Importantly, the fidelity of Alice learning Bob's bit can be made arbitrarily close to unity.