This article presents natural corner-based simultaneous localization and mapping (SLAM) using a new data association algorithm that achieves partial compatibility in a real unknown environment. In the proposed corners’ extraction algorithm, both the end points of an extracted line segment far away from the other segments and the intersection point of the two closer line segments are considered as corners. In data association, a partial compatibility algorithm obtaining a robust matching result with low computational complexity is proposed. This method divides all the extracted corners at every step into several groups. In each group, the local best matching vector between the extracted corners and the stored ones is found by joint compatibility, while the nearest feature for every new extracted corner is checked by individual compatibility. All these groups with the local best matching vector and the nearest feature candidate of each new extracted corner are combined, and its joint compatibility is checked with the linear matching time. The experimental results in an indoor environment with natural corners show the robust matching result and low computational complexity of the partial compatibility algorithm in comparison with individual compatibility nearest neighbor and joint compatibility branch and bound.