In this Letter we present the first implementation of a quantum coin-tossing protocol. This protocol belongs to a class of "two-party" cryptographic problems, where the communication panners distrust each other. As with a number of such two-party protocols, the best implementation of the quantum coin tossing requires qutrits, resulting in a higher security than using qubits. In this way, we have also performed the first complete quantum communication protocol with qutrits. In our experiment the two partners succeeded to remotely toss a row of coins using photons entangled in the orbital angular momentum. We also show the experimental bounds of a possible cheater and the ways of detecting him.