Dzieje się tak, ponieważ A* tworzy „optymistyczne” oszacowanie kosztu ścieżki przez każdy węzeł, który bierze pod uwagę – optymistyczny w tym sensie, że prawdziwy koszt ścieżki przez dany węzeł do węzła końcowego będzie co najmniej tak duży jak oszacowanie.
Kiedy A* kończy przeszukiwanie, ma (z definicji) znalezioną ścieżkę, której koszt jest mniejszy niż szacowany koszt jakiejkolwiek innej ścieżki (innej, czyli przechodzącej co najmniej przez jeden węzeł niewchodzący w skład znalezionej ścieżki). Ponieważ oszacowania są optymistyczne, algorytm A* może bezpiecznie zignorować te inne ścieżki. Innymi słowy, A* nigdy nie „przeoczy” ścieżki o niższym koszcie i dlatego jest dopuszczalny.
Przypuśćmy teraz, że jakiś inny algorytm B kończy swoje przeszukiwanie ze ścieżką, której koszt jest nie mniejszy niż szacowany koszt ścieżki przez jakiś węzeł X niewchodzący w skład znalezionej ścieżki. Algorytm B, bazując na informacjach wynikających z posiadanej heurystyki, nie może wykluczyć możliwości, że ścieżka przez węzeł X może mieć niższy koszt niż znaleziona ścieżka. Z tego wynika, że jeśli B bierze pod uwagę mniejszą liczbę węzłów niż A*, to B nie jest dopuszczalny.