La historia de Captain Star involucra a la tripulación del cohete espacial Boiling Hell, a la que se le ha ordenado que viaje a un planeta desierto conocido como "El Planeta Sin Nombre". La tripulación está formada por el ya mencionado Capitán Jim Star, que es egocéntrico, paranoico y el héroe explorador más grande del universo; la Primera Oficial Scarlette, la científica; el Ingeniero Atómico Stoker Jones, que sufrió un accidente atómico que lo hizo mutar y ahora tiene nueve cabezas y seis brazos; el Navegante Black, que es el dueño y cocinero de un restaurante repleto de peceras con peces; y al final se une un robot llamado Jim-Bob-Bob, que se encarga de la lavandería y otros trabajos.

Captain Star es descrito en la apertura como: "el más grande héroe que cualquier mundo jamás haya conocido". Es un explorador legendario que tiene centenares de planetas nombrados como él. Su cumpleaños es un día de fiesta en todo el universo. A lo largo de la serie, los personajes esperan órdenes adicionales del Control de Misión que nunca llegan. No está claro si el Control de Misión simplemente se ha olvidado de Star y su tripulación, ahorrándole la indignidad de obligarlo a retirarse y manteniéndolo en servicio activo para que pueda seguir siendo un héroe para el público. Sin embargo, los acontecimientos que ocurren dentro y fuera del planeta, frecuentemente requieren la intervención de Star.

• Capitán Jim Star: Preparado desde su nacimiento para ser un capitán de nave espacial, el Capitán Star es considerado como el mayor capitán de la flota. Salió de la Academia de Capitanes a los 12 años para pasar un año como aprendiz con el capitán Ned Nova del Merry Cheeser, que había nombrado 115 planetas, que fue el mayor récord hasta que Star lo superó. El Capitán Star tiene aproximadamente 127 "años espaciales", lo que parece convertirlo en un hombre de unos cincuenta años en su sociedad. No es humilde, aunque tampoco es excesivamente arrogante, Star se cree un héroe y se siente merecedor de su aclamación universal. A menudo es ajeno al peligro y a los consejos y preocupaciones de su tripulación.

• Primera Oficial Scarlette: Una mujer fuerte y sin miedo, y una científica consumada. Scarlette a menudo salva el día a través de sus esfuerzos científicos. La lógica y la naturaleza investigativa de Scarlette son un claro contraste con la tendencia del Capitán Star a improvisar en una emergencia. En El Planeta Sin Nombre, donde el Capitán Star no tiene ninguna nave para ordenar o aventuras para conducir, Scarlette maneja la mayor parte de sus deberes de mando.

• Ingeniero Atómico Stoker Jones: Sufrió un accidente atómico que lo hizo mutar y ahora tiene nueve cabezas y seis brazos. Cada una de las cabezas de Jones alberga una parte diferente de su cerebro, haciendo que cada cabeza tenga una personalidad ligeramente diferente. Jones es un gran amante de los gatos. Las conversaciones entre las muchas cabezas de Jones y otros miembros de la tripulación a menudo los llevan a ser impacientes y molestos con él.

• Navegante Black: Navegante Black prepara un pequeño restaurante en forma de pez en El Planeta Sin Nombre y se convierte en el cocinero. Obsesionado con el pescado, el restaurante está lleno de acuarios y peceras. Black a menudo nada con sus peces, e incluso crea un dispositivo de interfaz cerebro-computadora que representa sus pensamientos. Black tiene un temperamento nervioso y a menudo sufre pánico bajo presión.

• Capitán Bloater
• Jasper Quilt
• Capitán Spratt