The life of the 366th Security Forces Squadron began on 15 November 1952, when the unit was constituted as the 366th Air Police Squadron. This action created the unit only on paper, with the squadron first activated on 1 January 1953 at Alexandria Air Force Base, Louisiana. At the time of this activation, the squadron was assigned to the 366th Air Base Group of the newly created 366th Fighter-Bomber Wing. The Air Police Squadron continued to provide security services at Alexandria, later renamed England AFB, until 25 September 1957. On this date, a reorganization of forces at the base made the 366th Fighter-Bomber Wing a tenant unit, with security and other support functions provided by another unit. The 366th Air Police Squadron remained inactive until 26 January 1966, when it was activated and assigned to the Pacific Air Forces.

This assignment involved the unit designation only, with the squadron gaining personnel and equipment two weeks later when it was organized and assigned to the 366th Combat Support Group at Phan Rang Air Base, South Vietnam. Later that year the squadron and the rest of the wing relocated to Da Nang Air Base, South Vietnam, arriving on 10 October 1966. While at Da Nang, the unit designation was changed from Air Police Squadron to its present name of the 366th Security Police Squadron on 15 May 1967. The unit remained at Da Nang for almost six years, before being sent to its final base in Southeast Asia on 27 June 1972. This stay at Takhli Royal Thai Air Force Base, Thailand proved brief, however, with the squadron departing for assignment to Mountain Home Air Force Base, Idaho on 31 October 1972. Between 1972 and the Persian Gulf War, the 366th Security Police Squadron has provided security and law enforcement services both at Mountain Home and various deployed locations such as Southwest Asia and Central America.

In 1991, thirty-six personnel deployed in support of Operation Desert Shield/Desert Storm to various locations in the Kingdom of Saudi Arabia. These personnel were comprised of a Mk-19 team, a MWD team, a security squad, and a partial flight. During the next year, the unit deployed personnel to south Florida in support of recovery operations after Hurricane Andrew. That same year, Gunslingers were sent to Cuba to assist with the Haitian refugees. When the Air Force designated the 366th Wing in 1993 as "America's First Air Intervention Composite Wing" the mission of the Gunslingers changed. The squadron provided security for and was tasked to field test new security concepts for the composite wing during deployments to Volk Field, WI and BrightStar 94 in Cairo, Egypt.

The operations tempo for the squadron did not slow down in 1995. The unit participated in the largest "fly away" Operational Readiness Inspection in the history of the Air Force. Named Operation Northern Pike, the event took eight months of planning involving twenty-four bases, six operation locations and 4,000 troops. The squadron received an "Outstanding" and "Excellent" in the two phases of this inspection. In addition, the unit assisted in Operation Sea Signal, Guatanamo Bay, Cuba providing security for 30,000 Cuban refugees.

Shortly after the unit was redesignated as the 366th Security Forces Squadron, the unit deployed to Bahrain to support the wing during Air Expeditionary Force V. The wing and the Gunslingers again made the history books when they earned across the board "Excellent" ratings during the Air Force's first ever Operational Readiness Inspection conducted during a real world contingency deployment.

It was during this deployment that the 366th Security Forces Squadron was recognized for "writing the book on modern Force Protection" by CENTCOM Joint Readiness Area Coordinator. The unit was also praised as the "Best Security Operation In Theater {CENTCOM}". The unit was again recognized for the development of a "Force Protection Cell" comprised of Security Force personnel, AF Office of Special Investigation Agents, and wing Intel troops. This cell was recognized as the Best Counterintelligence Operation in the Air Force, 1997, and received a First Honorable Mention Award from the DoD Antiterrorism Awards Program, 1997.

The 366th Security Forces Squadron has been recognized as the Best Medium Sized Security Forces Unit, Air Combat Command, in 1995, 1997, and 1998 and was recognized as the Best Medium Sized Security Forces Unit, Air Force, 1997.

Awards earned by the unit include a Presidential Unit Citation, five Air Force Outstanding Unit Awards with Combat "V" devices, seven peacetime Air Force Outstanding Unit Awards, the Republic of Vietnam Gallantry Cross with Palm, and fifteen campaign streamers from Vietnam.