Contrastive learning allows us to flexibly define powerful losses by\ncontrasting positive pairs from sets of negative samples. Recently, the\nprinciple has also been used to learn cross-modal embeddings for video and\ntext, yet without exploiting its full potential. In particular, previous losses\ndo not take the intra-modality similarities into account, which leads to\ninefficient embeddings, as the same content is mapped to multiple points in the\nembedding space. With CrossCLR, we present a contrastive loss that fixes this\nissue. Moreover, we define sets of highly related samples in terms of their\ninput embeddings and exclude them from the negative samples to avoid issues\nwith false negatives. We show that these principles consistently improve the\nquality of the learned embeddings. The joint embeddings learned with CrossCLR\nextend the state of the art in video-text retrieval on Youcook2 and LSMDC\ndatasets and in video captioning on Youcook2 dataset by a large margin. We also\ndemonstrate the generality of the concept by learning improved joint embeddings\nfor other pairs of modalities.\n