La primera que hace mención de la Compañía Gris, es Galadriel, quien le envía un mensaje a Aragorn a través de Gandalf:

¿Dónde están ahora los Dúnedain, Elessar, Elessar? ¿Por qué tus gentes andan errantes allá lejos? Cercana está la hora en que volverán los Perdidos y del Norte descienda la Compañía Gris. Pero sombría es la senda que te fue reservada: los muertos vigilan el camino que lleva al Mar. (ESDLA)

Más adelante, tras la Batalla del Abismo de Helm, y cuando los Rohirrim están acantonando sus tropas para acudir en ayuda de Gondor tras el aviso con la flecha roja, Aragorn, Legolas, Gimli y Merry que cabalgaban junto a Théoden y Éomer, se encuentran con una compañía de hombres que están buscando a Aragorn, el día 6 de marzo de 3018 de la Tercera Edad. La compañía estaba integrada por Halbarad, primo de Aragorn, Elladan y Elrohir, hijos de Elrond y hermanos de Arwen y treinta montaraces del norte, armados de lanzas, arcos y espadas y vestidos con oscuros mantos grises. Cabalgaron hasta encontrar a Aragorn, junto a quien querían luchar. Halbarad portaba consigo un estandarte que Arwen había hecho para Aragorn y un mensaje:

Cortos son ahora los días. O nuestras esperanzas se cumplirán, o será el fin de toda esperanza. ¡Adiós, Piedra de Elfo! (ESDLA)

Elladan y Elrohir también le traían a Aragorn un mensaje de Elrond:

Los días son cortos. Si el tiempo apremia, recuerda los Senderos de los Muertos.(ESDLA)

Tras este encuentro, Aragorn consulta la Piedra de Orthanc y decide marchar por Los Senderos de los Muertos (como ya le habían aconsejado Galadriel y Elrond), por lo que se separa de Merry, Éomer y Théoden, que deben acabar de reclutar gente para poder acudir en ayuda de Gondor. Y es la compañía Gris la que atraviesa el funesto camino, cumpliendo la antigua profecía de Malbeth el Vidente.

Tras el juramento en la Piedra de Erech, los muertos siguen a la Compañía Gris hasta Pelargir, donde les ayudan a hacerse con los barcos de los Corsarios. De esta manera, destruyen una de las fuerzas de Sauron que estaba presta para atacar Gondor. Y la Compañía Gris, junto con los Hombres que se les unen al remontar el Anduin, consigue llegar a tiempo a Pelennor para unirse a la lucha y derrotar al ejército de Sauron.