Goombario es el primero que se une a Mario en Paper Mario. Su personalidad es muy parecida a su sucesora en Paper Mario 2, Goomarina.

Cuando Mario se cae inconsciente en el Pueblo Goomba al principio de Paper Mario, Goombario y su familia (Goombaria, Goompa, Gooma, Goomama y Goompapa) le encuentran y le deja descansar en la posada de Toad. Kammy Koopa ataca el pueblo y Mario les cuenta su misión. Goompapa sugiere que Goombario se una a Mario a la aventura, y él acepta. Goombario es muy inteligente, puede ayudar a Mario dándole detalles de los lugares en que se encuentran e información de los personajes que se encuentran a lo largo de su aventura. Sabe Cabezazo y Descripción de inicio. El primero propicia un gran cabezazo al oponente después de un gran salto y el segundo hace una detenida información del enemigo para enseñarte las claves de cómo derrotarle. Puede aprender Carga que le permite cargar energía y aumentar el daño de su próximo cabezazo (nivel super) y Multicabezazo que propicia cabezazos al oponente hasta que falles en el comando de acción (nivel ultra).

Su nombre aparece en la pantalla de resultados en Mario Golf Toadstool Tour. También en Super Paper Mario aparece en forma de carta en el vigésimo piso del subterráneo.

Kooper es el segundo miembro que se une al equipo de Mario. Es un koopa azul, que le encanta la aventura, parece joven y su sueño desde pequeño quiere llegar a ser un aventurero como su ídolo, el famoso arqueólogo Kolorado. Tiene una personalidad totalmente opuesta a la de sucesor Koops de Paper Mario 2, no obstante sus técnicas de combate son prácticamente idénticas.

Mario y Goombario al llegar al Pueblo Koopa encuentran que los Fuzzies han atacado el pueblo y se dedicaban a robar todos los caparazones de los Koopas del pueblo. Mario logra recuperarlos y entregárselos a sus propietarios. En esa misión se encuentra con Kooper, el cual le cuenta a Mario que su caparazón azul había sido robado por un Fuzzy y Mario como buen héroe se compromete a recuperarlo. Una vez Mario le recupera el caparazón y se lo entrega a Kooper, éste decide unirse al equipo. Su habilidad de introducirse en su caparazón y Mario poder empujarle le permite alcanzar objetos y activar interruptores lejanos pero que no podrías acceder de otro modo.

Kooper sabe Lanzaconcha que golpea a un enemigo con su caparazón y Super Concha que ataca a todos los enemigos situados en el suelo. Puede aprender Concha Mareo y Concha Fuego, el primero puede marear a los enemigos y el segundo quemarlos.

Bombette es el tercer miembro que se une al equipo. Cuando Mario entra en la fortaleza de los Hermanos Koopa, un Koopa encierra a Mario en una celda. Allí, Mario conoce a Bombette, una Bob-omb rosa con una mecha que fue atrapada en la fortaleza por haber explotado al lado de los Hermanos Koopa. Bombette ayuda a Mario explotando para crear un agujero por el cual escapar. Entonces ella se une al equipo de Mario. Con su habilidad para explotar puede destruir paredes agrietadas, activar interruptores y atacar a enemigos. Una vez a ayudado a Mario a acabar con los Hermanos Koopa, ella decide unirse a Mario para la consecución de los espítus estrella.

En los combates, Bombette puede usar Carga Cuerpo para explotar junto al enemigo o bien puede usar el ataque Bomba. Después puede aprender ataques más poderosos como Super Bomba que golpea a todos los enemigos terrestres o Mega Bomba que causa daño a cualquier enemigo que se encuentre en la batalla. En el juego Bombette había roto recientemente con un Bob-Omb. Él normalmente le pide que vuelva con él, pero ella rechaza siempre su oferta.

El nombre de Bombette probablemente proviene de una combinación de bomba, refiriéndose al aspecto de su familia y la naturaleza (los Bob-Ombs), y -ette, un sufijo semicomún de nombres femeninos, sobre todo de lenguas como el francés.

Parakarry es el cuarto compañero en las filas de Mario. Es un Koopa Paratroopa y es el principal cartero en el Mushroom Kingdom. De hecho, al principio del juego, Parakarry entrega la invitación de Peach al buzón de los hermanos Mario, una carta que marcará el inicio de los eventos de Paper Mario. Asimismo aparece al inicio de Paper Mario 2: La puerta Milenaria entregando del mismo modo una carta a Mario de Peach e iniciando así una nueva aventura, provocando un inicio totalmente idéntico al Paper Mario original. Parakarry trabaja para Correos en Ciudad Toad, la capital del Reino Champiñón. A pesar de que es bueno en su trabajo, es muy torpe y a menudo pierde las cartas que él, como se supone, debe entregar, y también se aprecia en el juego que es bastante lento en el entregamiento del correo, como el hecho encontrarse cartas suyas por todo el reino.

El primer encuentro con Mario es en el Monte Escarpado. (Aunque en ocasiones se le pueda encontrar de pie en correos, antes del capítulo primero para ser exacto). El cartero explica al fontanero que ha perdido tres cartas y pregunta a Mario que le ayude a recuperarlas. Mario recupera las cartas y se las devuelve a Parakarry, el cual le pide unirse a su equipo para ayudarle y recuperar otras cartas que ha perdido y entregárselas a sus destinatarios. Fuera de la batalla Parakarry puede llevar por los aires a Mario durante un previo periodo de tiempo, suficiente como para superar llegar a plataformas que no podrías llegar de otra forma. Mario podrá hablar con la gente a la que entrega las cartas y enterarse de qué tratan (estando Parakarry como acompañante). Su nombre es una fusión entre "Paratroopa" (Koopa volador) y la palabra "carry" que significa "llevar", como él es un cartero y cuya habilidad consiste en llevar a Mario. O también puede ser el nombre Karri unido a la palabra Paratroopa.

Parakarry sabe Picado (propicia una patada), Tiro Concha (Parakarry se esconde en su concha y sale disparado contra su enemigo con gran potencia) y puede aprender Viaje Aéreo (echa a los enemigos del combate) y Asalto Aéreo donde Parakarry vuela a gran velocidad de un lugar a otro infligiendo daño a todos sus adversarios.

Watt es el sexto miembro en unirse al equipo de Mario. Está encerrada en una lámpara de la Caja de Juguetes de los Shy Guy. Se encuentra encerrado dentro de una linterna que lleva un fantasma en el interior de una habitación oscura. Sólo se puede derrotar a ese enemigo si hay luz que se consigue golpeando la linterna y vencerle. Sólo puedes golpearle si hay luz. Ella cuenta a Mario que oyó a unos Shy Guys hablar de él y ella voluntariamente decide unirse a él en su misión. Watt posee ataques eléctricos y tiene la habilidad de iluminar áreas oscuras y revelar bloques invisibles e ítems. En nivel Normal le da al enemigo un shock eléctrico con el ataque Calambrazo (ataque muy útil ya que puede atravesar los puntos de defensa del enemigo), además de un ataque paralizante a un enemigo con Electroshock. En nivel Super aprende Turbo Carga con lo que puede recargar a Mario para que sus ataques hagan más daño por un lapso de tiempo. En nivel Ultra aprende Mega Shock y puede lanzar una poderosa descarga electrica que en caso de funcionar paralizaría a todos los enemigos.

En Ciudad Toad, Watt recibe dos cartas, una de su madre y otra de Fuzzipodo. Por lo tanto de Watt se conoce que tiene una madre, a quien todavía no se ha visto ni se le conoce el nombre. Watt habla ocasionalmente de ella e incluso recibe una carta suya en la oficina de correos. No obstante, Watt nunca menciona a su padre. Aunque Watt es hembra, a veces se refieren a ella como "él". Aunque su edad no ha sido confirmada todavía, todo hace pensar que es muy joven debido al chupete que lleva siempre en la boca.

Sushi es el penúltimo compañero de Mario en Paper Mario. Descansa en un árbol de la Jungla Jade en el Pueblo Yoshi en la isla Lavalava. Ella es una gran cuidadora, aficionada a los culebrones y le encanta cotillear. Cuando Mario se encuentra con ella que busca desesperadamente a unos pequeños Yoshis que se han perdido. Mario, como buen héroe que es decide ayudarla. Una vez Mario los ha encontrado a todos, le cuenta a Sushi su misión de rescatar a la princesa. Sushi dice que es una historia muy romántica y decide unirse. Permite a Mario navegar por el agua y bucear bajo ella. Sushi tiene una hija llamada Sashimi. Tanto Sushi como Sashimi corresponden a nombres de peces crudos de platos japoneses.

En nivel Normal golpea al enemigo con un potente Barrigazo, además de escupir agua con Mojar, ideal frente a enemigos de fuego. En nivel Super con Cubo Agua puede encerrar a Mario en un bloque de agua para incrementar su defensa por un lapso de tiempo. En nivel Ultra aprende Maremoto, que crea una gran marejada que golpea a todos los enemigos.

Lakilester, el último en unirse a las filas de Mario, formaba parte de los hombres de Huff N. Puff pero se une al equipo de Mario al vencerlo en Campos Floridos. Lakilulu, un Lakitu hembra interviene para que Mario no acabase con Lakilester tras ser derrotado. Se hace el duro para impresionar a su novia Lakilulu aunque a ella le gusta tal y como es. Lakilester Permite "flotar" a Mario sobre pinchos y lava y también le permite ir más rápido. Cambió su nombre porque pensaba que Lakilester era un nombre muy feo, a si que se llama a sí mismo Spike (Jonathan en japón).

En nivel Normal con Huevo Pinchos lanza un pincho que si da en el blanco causa daño o puede también lanzar una ráfaga de pinchos con Tropel Pinchos con los que no importa apuntar ya que daña a todos los enemigos. En nivel Super, con Refugio Nube puede rodear a Mario con una nube que aumentan las probabilidades de esquivar los ataques enemigos por un lapso de tiempo. En nivel Ultra con Huracán puede crear un poderoso huracán que arrastra a todos los enemigos fuera del combate.

Goomarina es una Goomba y la primera que se une al grupo de Mario. Es alumna aventajada de arqueología del profesor. Lleva un casco de minero, y es admiradora de Mario. Como es muy lista le informa de donde está en cada momento e incluso qué hay que hacer, también posee una gran sabiduría popular por lo que conoce y puede contarte cosas acerca de la gente que se encuentren por el camino. En el combate atacará con cabezazos y multicabezazos, podrá describir a los enemigos para conocer sus habilidades, y usar el beso de ánimo.

Koops es un Koopa Troopa con una tirita que vive en Villa Verde, ha llevado una vida relajada y ahora quiere ser aventurero. Su padre desaparecido en el Castillo de Gombaba también lo era y en principio se une a Mario para buscarlo. Puedes saltar sobre él para lanzar su caparazón, que puedes mantener en el aire el tiempo que se desse. Es muy útil para alcanzar objetos lejanos o pulsar interruptores. En el combate Koops se lanzará contra sus enemigos golpeándolos con el caparazón. Sus ataques especiales son: Lanzaconcha, Súper Concha, Protegeconcha y Concha Furia.

Claudia es un espíritu de nube, con aspecto de cantante de ópera y con predilección por el bigote de Mario, le llama Pichoncito. Ansía volver a los escenarios y acompañará a Mario para conocer mundo. Era una gran actriz, tan famosa que no existía nadie que no hubiera oído hablar de ella. Pero el brillo del glamour oculta la sordidez de un mundo oscuro, algo realmente despreciable, ella no encajaba allí y por eso se fue a vivir en el Bosque Maravilloso, con los Punis. Su poder consiste en soplar, es útil para mover algunos objetos, y sobre todo para revelar secretos en el escenario. En el combate se arrojará directamente, en toda su plenitud, contra los enemigos, con su Placaje, o bien causará un Vendaval, un Achuchón o una Cortina Humor. En la versión anglosajona Flurrie significa ráfaga, un nombre ideal para este personaje.

Un yoshi recién nacido con cara de pocos amigos y con una vistosa cresta. Iba a convertirse en aderezo especial para perritos calientes en Ciudad Dojo. Por suerte Mario lo libera de tan terrible destino. Este personaje se puede personalizar en dos aspectos, uno es el nombre y el otro es el color, cualquier color habitual de los yoshis. Mario puede montar en el yoshi para ir más rápido por el mapa, como es muy joven aún al pobre le cuesta pero va muy rápido. También puede revolotear en un corto espacio de tiempo, pero es fundamental para avanzar en ciertas áreas. En el combate yoshi planea sobre las cabezas de los enemigos para luego arrojarse sobre ellos con su golpe Cadera, hace poco daño pero lo hace varias veces. También puede engullir al enemigo, lo que permite penetrar la defensa, arrojar huevos reductores y realizar una estampida.

Bibiana es un brujo (sí, es un chico) que conforma "el trío de las sombras" y se une a Mario en el Templo Lúgubre después de que Rumpel le robase su identidad. A Bibiana siempre le echaba la bronca su hermana mayor, sin motivo, y la castigaban mucho y de forma cruel por lo que ha cogido complejo de inferioridad. Como Mario la trata muy bien y la ayuda decide unirse a su grupo. Bibiana puede agarrar a Mario e introducirle debajo del suelo, por lo cual pasan desapercibidos para los enemigos. En el combate puede transportarse y propinar un buen puñetazo a los enemigos con su Golpe Sombra, además los dejará ardiendo algunos turnos. Podrá proteger a Mario con la habilidad transparencia, y usar ataques como Llamarada y Embelesamiento.

Bombard es un viejo Bomb-Ombs marinero, con timón incorporado y todo. Su pasado es una historia bastante lacrimógena, estuvo surcando los mares cuando su esposa falleció y por ello nunca más quiso volver a navegar. Se unirá a la aventura de Mario como timonel del barco El Temido en la aventura hacia Isla Trópico, pero costará convencerle, sólo una carta de su difunta esposa le hará cambiar de opinión. Posteriormente se unirá al grupo de forma definitiva. Bombard hace lo que mejor saben hacer los Bomb-Ombs, ¡Explotar!. Su explosión sirve para abrir paredes agrietadas o para pulsar interruptores y durante el combate eso provocará un enorme daño a los enemigos. Sus ataques son: Bomba, bomba tiempo, mina y gran explosión. Lo curioso es que por mucho que explota a él nunca le ocurre nada, habría que ver de qué material están hechos.

Lupina se cruza en varias ocasiones en el camino de Mario antes de que se una al grupo. Es una ratona ladrona, especialista en robar medallas, casualmente también es la dueña de la tienda de medallas que hay en Villa Viciosa. Lupina tiene muy buen olfato para los tesoros, si en la aventura empieza a olisquear, eso es que hay un tesoro cerca, una pieza estrella. Durante el combate Lupina da unos cuantos bofetones a sus enemigos, con la Bofetada del Amor, aunque también dispone de otros ataques como: Beso Furtivo, Confusión y Beso Cariñoso. El único compañero opcional, no es necesario para acabar el juego. Ella se unirá a ti si le entregas una medalla que olvidó en el Castillo de Gombaba. Existe un ratón, dentro del bar de Villa Viciosa que está enamorado de ella.