นิลส์ นิลสัน สร้างวิธีที่ใช้ฮิวริสติก มาเพิ่มความเร็วของขั้นตอนวิธีของไดค์สตราในปี ค.ศ. 1964 และเรียกขั้นตอนวิธีนี้ว่า A1 ต่อมาในปี ค.ศ. 1967 เบิร์ดแรม เรมเซสปรับปรุงขั้นตอนวิธีตัวนี้เพิ่มเติม แต่ไม่สามารถพิสูจน์ถึงความเร็วที่เพิ่มนี้ได้ เขาเรียกขั้นตอนวิธีนี้ว่า A2 ในปี ค.ศ. 1968 ปีเตอร์ อี ฮาร์ทแสดงการพิสูจน์ว่า A2 เป็นขั้นตอนวิธีที่เร็วขึ้นได้ และการพิสูจน์ของเขาได้แสดงอีกด้วยว่าขั้นตอนวิธี A2 เป็นขั้นตอนวิธีที่ดีที่สุดในเงื่อนไขที่กำหนด เขาจึงใส่คลีนสตาร์ (*) หลังตัว A เพื่อตั้งชื่ออัลกอรึทึมตัวนี้ซึ่งหมายถึง A และทุกรูปแบบของ A[2]