เนื่องจากความคับแคบของฐานบินสงขลาที่ไม่สามารถขยายเส้นทางวิ่งแล้ว และบริเวณโดยรอบเต็มไปด้วยชุมชน จึงมีการเสนอให้ก่อสร้างสนามบินแห่งใหม่ในปี พ.ศ. 2504 และว่าจ้าง บริษัท สเวอร์คลับ แอนด์ พาร์เชล โอเวอร์ซี จำกัด ให้สำรวจและออกแบบสนามบินแห่งใหม่ และพบว่าพื้นที่ที่มีความเหมาะสมที่สุดคือบริเวณบ้านควนลัง ตำบลคลองหอยโข่ง อำเภอหาดใหญ่ (ในเวลานั้น) เพราะอยู่ห่างไกลจากตัวเมือง และไม่ประสบปัญหาด้านการระบายน้ำ รวมถึงเป็นพื้นที่สงวนไว้ของจังหวัดสงขลาจึงทำให้ประหยัดงบประมาณแผ่นดินในการจัดซื้อที่ดิน และใช้ชื่อสนามบินแห่งใหม่ว่า สนามบินหาดใหญ่ ได้รับอนุญาตให้ใช้งานเป็นสนามบินอนุญาตเมื่อวันที่ 16 เมษายน พ.ศ. 2514 สังกัดกรมการบินพาณิชย์ กระทรวงคมนาคม[6] ซึ่งในเวลาเดียวกันกองทัพอากาศยังคงใช้งานสนามบินสงขลาเป็นฐานบิน และประจำการฝูงบิน 531 จากกองบิน 53 ประจวบคีรีขันธ์[3]

ต่อมากองทัพอากาศได้ย้ายฝูงบิน 531 ซึ่งสังกัดกองบิน 53 ประจวบคีรีขันธ์ มายังที่ตั้งของฐานบินหาดใหญ่ในปัจจุบันเมื่อวันที่ 5 ตุลาคม พ.ศ. 2518 ในชื่อ ฝูงบินผสม 536 (หาดใหญ่) และเปลี่ยนชื่อเป็น ฝูงบินอิสระปฏิบัติราชการสนาม 536 เมื่อวันที่ 25 กันยายน พ.ศ. 2520[3]

เนื่องจากภัยคุกคามของโจรจีนคอมมิวนิสต์ในพื้นที่ กองทัพภาคที่ 4 จึงได้อนุมัติให้พัฒนาฐานบินหาดใหญ่ขึ้นเป็นกองบินปกติเลขสองตัว (เพื่อพลางก่อน) และเปลี่ยนชื่อจาก ฝูงบินอิสระปฏิบัติราชการสนาม 536 (หาดใหญ่) เป็น กองบิน 56 ในวันที่ 27 พฤศจิกายน พ.ศ. 2523 ทำให้วันนี้เป็นวันคล้ายวันสถาปนากองบิน 56 ต่อมาได้มีการโอนสายการบังคับบัญชาขึ้นต่อกองบิน 71 เปลี่ยนชื่อเป็น ฝูงบินอิสระปฏิบัติราชการสนาม 716 (หาดใหญ่) โดยรัฐมนตรีว่าการกระทรวงกลาโหมได้อนุมัติให้กองทัพอากาศใช้อัตรากองบินหมายเลขสองตัว คือ กองบิน 56 และยกเลิกฝูงบินอิสระปฏิบัติราชการสนาม 716 (หาดใหญ่) เมื่อวันที่ 30 กันยายน พ.ศ. 2526[3]

กองบิน 56 ได้รับโอนเครื่องบินแบบ ที-33 จำนวน 14 ลำ และเครื่องบินแบบ อาร์ที-33 จำนวน 3 ลำ จากกองบิน 1 ฝูงบิน 101 ฐานบินโคราชมาประจำการที่ฐานบินหาดใหญ่เมื่อวันที่ 15 มิถุนายน พ.ศ. 2524 มีภารกิจในการลาดตระเวนทางอากาศและฝึกนักบินขับไล่/โจมตี และปลดประจำการเครื่องบินไปเมื่อวันที่ 30 กันยายน พ.ศ. 2538 ปัจจุบันยังคงไม่มีอากาศยานเข้าประจำการในฝูงบินแต่อย่างใด[3]