Higher-order relations are important for various cognitive tasks, such as analogical transfer. The current study tested people’s ability to learn new relational categories, using a learning test of pure higher-order relations. Each stimulus consisted of 4 objects varying on 3 dimensions. Each category was defined by three binary relations between pairs of objects, producing six logically different conditions. Every category was composed of the same number of relations, but differed in the manner that the relations were linked (i.e., by operating on shared objects). Various learning models were compared and the significance of their performance on the experimental task is discussed. The current findings may advance understanding of the cognitive mechanisms involved in relational learning and the manner in which people naturally represent higher-order relational structures.