Online social networks (OSNs) have revolutionarily changed the way people connect with each other. One of the main factors that help achieve this success is reputation systems that enable OSN users to mutually establish trust relationships based on their past experience. Current approaches for the reputation management cannot achieve the fine granularity and verifiability for each individual user, in the sense that the reputation values on such OSNs are coarse and lack of credibility. In this paper, we propose a fine granularity attribute-based reputation system which enables users to rate each other’s attributes instead of identities. Our scheme first verifies each OSN user’s attributes, and further allows OSN users to vote on the posted attribute-associated messages to derive the reputation value. The attribute verification process provides the authenticity of the reputation value without revealing the actual value to entities who do not have the vote privilege. To predict a stranger’s behavior, we propose a reputation retrieval protocol for querying the reputation value on a specific attribute. To the best of our knowledge, we are the first to define a fine-grained reputation value based on users’ verified attributes in OSNs with privacy preservation. We provide the security analysis along with the simulation results to verify the privacy preservation and feasibility. The implementation of the proposed scheme on current OSNs is also discussed.