We present a method for finding cross-modal space-time correspondences. Given two images from different visual modalities, such as an RGB image and a depth map, our model finds which pairs of pixels within them correspond to the same physical points in the scene. To solve this problem, we extend the contrastive random walk framework to simultaneously learn cycle consistent feature representations for cross-modal and intra-modal matching. The resulting model is simple and has no explicit photoconsistency assumptions. It can be trained entirely using unlabeled data, without need for any spatially aligned multimodal image pairs. We evaluate our method on challenging RGB-to-depth and RGB-to-thermal matching problems (and vice versa), where we find that it obtains strong performance.