The West Virginia State Police was created in 1919 in response to violence arising from attempts to unionize the state's coal miners and the resulting resistance by the coal operators.

Governor John Jacob Cornwell was the leading advocate of a state police force. He found sheriffs and constables ineffective, having to face periodic reelection and tending to take sides in labor struggles. Coal companies paid some deputy salaries in coalfield counties, and deputies moonlighted as private security guards. The private guard system angered workers and labor leaders, as did use of the National Guard during the bloody Paint Creek-Cabin Creek strike of 1912—13. Besides, the process of reestablishing the National Guard after World War I did not begin until April 1921.

Labor leaders ardently opposed the police bill, but the legislature passed it anyway. Cornwell signed it into law on March 31, 1919, effective June 29. The agency was designated the Department of Public Safety. The governor appointed Jackson Arnold, grand-nephew of Gen. Thomas J. "Stonewall" Jackson and former executive officer of the 1st West Virginia Infantry, as first superintendent. Departmental headquarters was located in Charleston, and there were two field companies, with an authorized strength of 125 men. The first trooper, Sam Taylor, enlisted on July 24.

Colonel Arnold faced daunting obstacles in recruiting, uniforming, and equipping the force. Newly enlisted troopers were required to bring their World War I uniform when reporting.

Company B, commanded by Capt. James R. Brockus, was based in Williamson, the county seat of Mingo County and a center of labor troubles. The July 1920 United Mine Workers strike there continued at varying levels until October 1922. Duty in "Bloody Mingo" eventually absorbed 90 percent of State Police strength, and three troopers were killed there. The State Police also helped defend Logan County against the miners' armed march during the 1921 Battle of Blair Mountain.

Following the trouble in the south and a period battling strike violence in the state's northern coalfields, the force shifted its focus to rural law enforcement and traffic safety. Because there were few paved roads in West Virginia before World War I, the State Police initially rode horses. But in September 1929 traffic regulation and road law enforcement became a State Police responsibility. Highway patrol quickly became the agency's major function, so automobiles and motorcycles replaced the troopers' horses. The force was also heavily engaged in enforcing Prohibition and in fighting gambling, prostitution, and illegal drug distribution.

State Police field structure grew to four companies in 1921, shrank to two in 1933, expanded to four again by 1936, and remained there until the Turnpike Division was added in 1954. A Criminal Investigation Bureau was organized in 1933 under later Capt. Charles W. Ray, to centralize arrest and conviction records. The Highway Safety Bureau and the forensic chemistry laboratory were added in 1936, and a Radio Division in 1939. FBI Director J. Edgar Hoover cited the West Virginia State Police as one of the nation's four leading law enforcement agencies in 1936.

Military leave caused a 40 percent shortfall in State Police strength during World War II. Ordinary crime and highway traffic declined during the war, but these duties were offset by war-related work such as personnel background investigations, military convoy security, and assisting selective service and ration boards.

After the war, the State Police realized a long-cherished goal by opening its academy at Institute, near Charleston, in October 1949. Captain Ray was the first director. Department headquarters relocated from the capitol building to new facilities in 1970. The first African-American trooper enlisted July 10, 1967, and resigned May 15, 1969. On May 16, 1977, the first female member enlisted, serving until 1997.

Today, the West Virginia State Police functions under the Department of Military Affairs and Public Safety.

As of 2005, there were 629 uniformed members, with 325 civilian employees performing administrative, communications, forensics, and other support tasks. In a major 1998 reorganization, "troop" designations replaced former companies. Today there are seven field troops, including one for the West Virginia Turnpike, one designated as the Bureau of Criminal Investigations, and one for Headquarters. There are 60 State Police detachments statewide.

As of 2012, 40 State Police troopers have died in the line of duty.