พญาเต่างอยตั้งอยู่ที่สวนสาธารณะอำเภอเต่างอย ริมลำน้ำพุง จังหวัดสกลนคร พญาเต่างอย ถูกกล่าวขึ้นราว 400 ปี โดยไทยได้ทำสงครามกับลาว คนลาวพ่ายแพ้จึงถูกกวาดต้อนมาอยู่ในประเทศไทย เมื่อเดินทางมาถึงลำน้ำพุง ซึ่งเป็นลำน้ำขนาดใหญ่ของสกลนคร และมีเต่าอาศัยอยู่เป็นจำนวนมาก คนในสมัยก่อนเห็นว่าบริเวณนี้น่าจะมีพืชพันธุ์ธัญญาหารที่อุดมสมบูรณ์ เหมาะแก่การเป็นที่อยู่อาศัย จึงได้ตั้งถิ่นฐานขึ้น โดยตั้งชื่อว่า “หมู่บ้านเต่างอย” ตามสถานที่พบเห็นเต่าที่กำลังลอยริมฝั่งแม่น้ำ หมู่บ้านแห่งนี้จึงมีสัญลักษณ์เป็น รูปเต่า และได้ตั้งชื่ออำเภอว่า เต่างอย เต่างอย หมายถึง เต่าที่อยู่บนที่สูงหรืออยู่ริมตลิ่งหรือโขดหิน