We consider the problem of hiding sender and recipient of classical and quantum bits, even if all physical transmissions can be monitored. We present a quantum protocol for sending and receiving classical bits anonymously, which unlike all classical protocols, prevents later reconstruction of the sender. It appears that entangled quantum states are uniquely suited for anonymous transmissions. We then extend this protocol to provide sender and recipient untraceability for transmissions of qubits as well. In the process we also introduce a new primitive called anonymous entanglement, which may be useful for other protocols as well.