Relevance feedback, as a key component of content-based image retrieval, has attracted much research attention in the past few years, and a lot of algorithms have been proposed. Most current relevance feedback algorithms use dichotomy relevance measurement—relevance or non-relevance. To better identify the user’s needs and preferences, a refined relevance scale should be used to represent the degree of relevance. In this paper, relevance feedback with multilevel relevance measurement is studied. Relevance feedback is considered as an ordinal regression problem, and its properties and loss function are discussed. A new relevance feedback scheme is proposed based on a support vector learning algorithm for ordinal regression. Since the traditional retrieval performance measures, such as precision and recall, are not appropriate for retrieval with multilevel relevance measurement, a new performance measure is introduced, which is based on the preference relation between images. The proposed relevance feedback approach is tested on a real-world image database, and promising results are achieved.