Dos meses después de la fundación de la villa de Herrera, la Comandancia General de las Colonias Militares de Oriente, a cargo del general José María de Jáuregui, decidieron el establecimiento de una colonia militar en el Paso de Piedras Negras, la cual fue denominada, Colonia Militar de Guerrero en Piedras Negras, dado que la nueva colonia dependía de la aún villa de Guerrero, facultando al subinspector de las colonias militares, coronel Juan Manuel Maldonado para el cumplimiento de esta disposición, girándoles un presupuesto de 500 pesos para la compra de carretas, bueyes y herramienta, la construcción de la fortificación, las casas y abrir la brecha.

Previo a la fundación, ya con la disposición de crearla; el 7 de agosto de ese año, se midieron los terrenos en los ocho sitios de ganado mayor, de acuerdo a la ley correspondiente, levantando el croquis el comisionado del gobierno del Estado, don Marcial Borrego y el día 14 de ese mes, se estableció oficialmente, según lo reportó el coronel Juan Manuel Maldonado, dando fe de la terminación de las primeras construcciones, dejando así a la villa de Herrera totalmente fusionada a la nueva Colonia Militar. Los primeros militares que formaron esta guarnición fueron el coronel Juan Manuel Maldonado, que fungió como testigo, el capitán primero José María Andrade como la máxima autoridad de la colonia, estuvieron también, el alférez primero Ignacio Perea, el capitán segundo José María Sáenz, el teniente Julio Cenea, el alférez segundo Domingo San Miguel, el pagador José María Luna y 168 soldados más.

En el mes de diciembre de ese año, el capitán Andrade solicitó permiso para contraer nupcias con la señorita Josefa Liendo y después de la boda, esa noche muere el militar, dejando acéfalo su puesto hasta el mes de marzo de 1851, en que la Comandancia de las Colonias nombra al capitán primero José Antonio Arredondo, quien se desempeñaba como capitán segundo en la Colonia Militar de Camargo, como el nuevo titular. Fue corta la duración de la Colonia Militar, en agosto de 1855. Durante esa época, en mayo de 1852, se registraron dos grandes tormentas a las que el capitán Arredondo llamó “huracanes”, que dejaron grandes daños a la incipiente población y a las instalaciones militares.

Dados los abusos que generaban los militares del Fuerte Duncan en el hoy Eagle Pass, se analizó la posibilidad de reubicar la colonia al sur, en la margen derecha del río Escondido, donde hoy está Villa de Fuente, lo que se hizo en 1855, pero no se reubicó la colonia. El capitán José Antonio Arredondo tuvo que entregar el control de la población a las autoridades civiles en agosto de 1855, al conformarse la villa de Piedras Negras, retomando el nombre del sitio original en donde se creó la villa de Herrera en el conocido Vado de Piedras Negras, consolidándose el poder civil en la persona del Sr. Teodoro Herrera como Presidente Municipal, al que al año siguiente sustituyó Eleuterio Flores Bejarano, que se mantuvo hasta el año de 1861.