Fully autonomous vehicles are rapidly approaching realization and concerns regarding their safety and robustness are a prominent obstacle to their integration into society. A bottleneck of an autonomous vehicle’s safety is its ability to self-localize under all types of conditions. Self-localization is critical for the vehicle to route to a destination, for the vehicle itself to be tracked in case of theft, and in determining local traffic laws to operate harmoniously with other traffic and pedestrians. The global positioning system (GPS) is utilized by autonomous vehicles for self-localization, but the availability and reliability of GPS is not guaranteed in all situations, such as when GPS reception is weak or when an adversary is spoofing information. We address this problem by proposing a self-localization method for autonomous vehicles that does not require GPS at localization time. The framework herein describes the representation of a road network as a graph using the data made available by OpenStreetMap, and an encoding of street segments based on detected landmark objects. We derive the current state observer transition function from the resulting graph, and employ localization methods based on set distance and minimum cost paths to determine the most probable location of the vehicle given a sequence of observed landmarks. Through simulating vehicle traveling paths along a road network generated from real data of a region of Washington D.C., we evaluate the performance of our method for varying degrees of landmark observation error and analyze the algorithm’s time and memory complexity, demonstrating that the approach provides a feasible solution to the problem.