Martín Rodríguez cruzó el río Uruguay el 28 de enero de 1826, instalándose en Paysandú, donde se incorporaron varios contingentes provenientes de Buenos Aires y del interior de las Provincias Unidas.
Los cuerpos de Entre Ríos formaron el Regimiento n.º 1 de caballería, al mando del coronel Federico Brandsen; el batallón de Cazadores de Salta, que incluía también efectivos de Santiago del Estero fue transformado en el Regimiento n.º 2 de Caballería, al mando del coronel José María Paz, que los había llevado desde sus provincias de origen; desde Buenos Aires fueron enviados los Regimientos n.º 3, n.º 4 y n.º 16 de Caballería, al mando de los coroneles Manuel de Escalada, Juan Lavalle y José Valentín de Olavarría. El Regimiento n.º 15 era el que había organizado Gregorio Aráoz de Lamadrid, pero quedó en Tucumán, luchando en la guerra civil. Un Batallón de Cazadores al mando de Manuel Correa y uno de artillería ligera, al mando de Tomás de Iriarte, completaban el Ejército. Hasta entonces, eran solamente 2800 hombres, según el propio Rodríguez. El jefe de estado mayor era el general Miguel Estanislao Soler.
El sitio de Montevideo persistió a todo lo largo de la guerra; las tropas a órdenes de Oribe no eran suficientes para conquistar la plaza, pero aun así lograron un importante triunfo en el cerro de Montevideo y el arroyo Pantanoso el 9 de febrero, rechazando una salida de las tropas sitiadas. Posteriormente el general Lucio Norberto Mansilla dirigió el sitio durante algún tiempo, para dejarle nuevamente el mando a Oribe meses más tarde.
José María Paz participó en la Batalla de Ituzaingó, donde la mayor parte de su cuerpo fue diezmado; aun así tuvo una participación importante con sólo un centenar de hombres, por lo que fue ascendido al grado de general por disposición del general Carlos María de Alvear. Cuando este se retiró del Ejército en campaña, le hizo entrega interinamente del mando del Ejército Nacional y es nombrado Jefe del Estado Mayor General, pasando a ser el primer Comandante General de carrera en la Argentina.
Los orientales no tenían preparación militar adecuada, y sus jefes estaban divididos en dos facciones, dirigidas por Lavalleja y Rivera. Este se sublevó con todo su regimiento y se incorporó al ejército de Rodríguez, pero el jefe nacional lo transformó en el Regimiento n.º 8 de Caballería, al mando de Juan Zufriategui. Lavalleja ―a quien el ministro de guerra había ordenado ponerse a órdenes de Rodríguez―, desobedeció abiertamente a este y atacó Colonia, fracasando en su intento. Por su parte, Rivera, siguiendo órdenes de Rodríguez, atacó a Bento Manuel Ribeiro en su avance sobre Paysandú, derrotándolo. Pero se negó a continuar su avance y destruir el campamento enemigo en la costa del río Cuareim, e incluso avisó al jefe enemigo de las intenciones de Rodríguez. El 17 de junio, por exigencia de Lavalleja, Rodríguez envió a Rivera a Buenos Aires, informando de lo sucedido. El presidente ordenó arrestar a Rivera, pero en el mes de septiembre, este escapó hacia Santa Fe, donde se puso bajo la protección de Estanislao López.
Rodríguez inició la marcha a mediados de 1826 hacia sudeste, buscando incorporar las tropas orientales. Se instaló en Durazno, donde recibió nuevas incorporaciones. También envió ayuda a Ignacio Oribe, que comandaba las operaciones en Cerro Largo, que estaba siendo atacado por las fuerzas del jefe gaúcho Bento Gonçalves da Silva; pero este destruyó las avanzadas enviadas por Oribe y Paz a fines de julio.
En agosto, Rodríguez tuvo noticias de que iba a ser relevado del mando, por lo que marchó a Buenos Aires sin esperar el cambio. El general Alvear se hizo cargo del Ejército el 1 de septiembre. Se incorporó también el Regimiento de Colorados de las Conchas, milicias de caballería, al mando de José María Vilela, y los Coraceros, cuyo jefe era el oriental Anacleto Medina. Con los Batallones n.º 1, n.º 2, n.º 3 y n.º 5 ―al mando de Manuel Correa, Ventura Alegre, Eugenio Garzón y Félix Olazábal respectivamente― aumentó el número de efectivos de infantería, pero igualmente estaba en franca minoría, con solo 1500, contra 500 de artillería y 3116 de caballería. La vanguardia estaba ubicada en Durazno, y estaba formada por 2600 hombres, todos de caballería, comandados por Lavalleja, Laguna, los hermanos Oribe y Servando Gómez. El grueso del ejército se organizó junto al Arroyo Grande, al norte de Colonia.