El concepto de Policía Militar parte de la necesidad de disponer de personal dentro del ejército con la capacidad de mantener el orden especialmente de la tropa, seguridad y vigilancia en caso de conflicto armado en zonas sensibles, la retaguardia, prisioneros y de policía ante la población civil en territorios ocupados.

Su origen en España lo más parecido podría ser la Guardia Civil creada el 28 de marzo de 1844 bajo la dirección del mariscal de campo D. Francisco Javier Girón y Ezpeleta, II Duque de Ahumada tomando como base la idea de “cuerpo especial de fuerza armada de Infantería y Caballería” inicialmente formado por "14 jefes, 232 oficiales y 5769 guardias repartidos en 14 Tercios" estableciendose dos Reglamentos el de Servicio dependiente del Ministerio de Gobernación donde se relaciona su cometido de “la conservación del orden público, la protección de las personas y las propiedades (…) y el auxilio que reclame la ejecución de las leyes” y el Militar dependiente del Ministerio de la Guerra donde se relaciona "la organización con arreglo a criterios castrenses, los ascensos, dependencia, obligaciones, disciplina y estatuto del personal del Cuerpo".

Tras la Guerra Civil se crearon la Policía Naval y la Policía Aérea con la finalidad de proteger a autoridades militares "escoltas", las instalaciones, traslado de detenidos y al control de la tropa fuera de los acuartelamientos osea en las horas de paseo. El Boletín Oficial del Estado del 22 de septiembre de 1960 firmado por el ministro de la Gobernación Almirante Carrero Blanco establece la creación de la Policía Militar del Ejército de Tierra siendo esta década de los 60 donde se desarrolla la creación de las diferentes compañías de PM con un ambito territorial en función de las Capitanías Generales.

La Policía Militar de Las Palmas dispuso como acuartelamiento el conocido como Castillo de la Mata o Cuartel de Alvarado, antigua fortaleza cuyo origen se remonta a una antigua casa mata del siglo XVI que protegía la muralla y que al cabo de los siglos se fue ampliando. En este acuartelamiento la Policía Militar dispuso de una unidad a nivel de Sección compartiendo instalaciones con el III Tercio Banderín de Enganche de la Legión. El último reemplazo destinado de forma directa fue el 4º de 1978

En septiembre de 1979 al ser trasladas a la península las unidades de la 1ª Bandera Paracaidista "Roger de Flor" y la 2º Bandera Paracaidista "Roger de Lauria" sus instalaciones en el  Acuartelamiento de Las Rehoyas Bajas son ocupadas por la Policía Militar de las Palmas hasta entonces en el Castillo de la Mata y por otras dos unidades antes destinadas en la Isleta:una Compañía Mixta Mecanizada del Rgto. de Infantería Tenerife 49 y la Compañía 103 de las COEs del Rgto. de Infantería Canarias 50. El mal estado del acuartelamiento Las Rehoyas y su envejecimiento obligaron a que el personal nuevo destinado realizara un esfuerzo extra para su actualización y adecuación, literas, lavabos, duchas, armeros en las compañías, etc. los veteranos de aquellos meses recuerdan como otras satisfacciones la llegada de un televisor.

En enero de 1980 la Policía Militar de Las Palmas se organizó en dos compañías la 113 y la 114 manteniendose en el acuartelamiento de Las Rehoyas hasta primeros de los 90 en que se unifican en una denominandose Compañía de Policía Militar 83 hasta su traslado a la Isleta a mediados de los 90 donde permanece actualmente e integrada en el Batallón de Cuartel General de la Brigada "Canarias" XV en la Base General Alemán Ramírez.

- El Cuartel Castillo de la Mata que disponía de la catalogación de  Monumento Histórico Artístico desde 1949 fue instalación militar hasta 1997 y tras una profunda rehabilitación actualmente es Museo de la Ciudad y el Mar.

- El cuartel de Las Rehoyas construido a principios de los 50 dejó de ser de interés para Defensa siendo vendido en 1996 y actualmente son instaciones deportivas y parque público del Ayuntamiento de Las Palmas.