This paper proposes a novel approach to traffic state estimation using mobile phones. In this work, a real-time traffic data collection policy based on the so-called “3R” philosophy, a unique vehicle classification method, and a reasonable traffic state quantification model are proposed. The “3R” philosophy, in which the Right data are collected by the Right mobile devices at the Right time, helps to improve not only the effectiveness but also the scalability of the traffic state estimation model. The vehicle classification method using the simple data collected by mobile phones makes the traffic state estimation more accurate. The traffic state quantification model integrates both the mean speed capacity and the density of a traffic flow to improve the comprehensibility of the traffic condition. The experimental results reveal the effectiveness as well as the robustness of the proposed solutions.