Voyager sets down on a planet for a major maintenance overhaul while away teams in shuttles are sent in search of supplies. As Torres informs Captain Janeway that repairs will take days longer than originally expected, suddenly several consoles black out. Moments later the consoles flicker back on, and Icheb steps forward to explain the repair he made. Impressed, Janeway assigns Icheb to work with Torres, hoping he can help get the job done a little faster.
Harry Kim, Seven of Nine and Neelix are on the Delta Flyer searching for dilithium when they are caught in the crossfire between two alien ships. They receive a distress call from a Kraylor captain begging for help with casualties and claiming that his ship is on a humanitarian mission. Hesitant to get involved, Kim contacts the opposing ship, but the Annari commander there is very arrogant and charges weapons. Kim uses the Flyer's deflector to damage the Annari ship, forcing them to retreat. He and Neelix then beam over to the damaged Kraylor ship with medical kits and learn that the captain was killed along with all the ship's other officers. Kim sets out to repair the ship's engines and cloaking device, and impresses the Kraylor with his skills. When the ship is ready to fly again, Loken, the doctor in charge of the research team aboard, asks Kim to command the ship to their destination, since no one left alive among them is trained. Kim declines, but Loken insists that they can't afford to fail in their mission to deliver vaccines to their homeworld that will save thousands of lives. Since their flight plan will take them close to Voyager's location, Kim agrees to fly the ship that far.
When the cloaked Kraylor ship approaches the planet where Voyager is grounded, they discover three Annari warships in orbit. It turns out the Annari are attempting to befriend the Voyager crew and become trading partners. Once the Annari leave the planet, Kim brings Loken to Voyager, where he appeals to Captain Janeway for help getting home. In private, Janeway tells Kim that he has put her in a difficult position, but Kim presses the case on behalf of the Kraylor, and offers to take charge of the mission himself. He notes that after seven years on Voyager he's still an ensign, and wants a chance to prove himself as a commander. Janeway agrees, but orders him to take Seven along.
After getting a lesson in decisiveness from Neelix, Kim enters the bridge of the Kraylor ship with authority and lays in a course. He renames the ship "Nightingale" after the famous wartime nurse from his homeworld. He then prepares the ship for departure and gives the command to engage. During the flight, Seven informs Kim that she asked the acting helmsman, Terek, to make a course correction. Over Seven's objection, Kim goes to check up on the crewman and ends up doing the job himself.
Meanwhile on Voyager, Icheb has been working with Torres, who invited him to go rock climbing with her on the holodeck. After he gets advice from the Doctor on how to tell if someone has romantic feelings for another, Icheb thinks he's getting "signals" from Torres while working very closely with her in a Jefferies Tube, and even scans her for the physiological responses the Doctor described.
On the Nightingale, an alarm sounds and the cloak destabilizes. Kim orders all stop and works in Engineering with Seven and crewman Dayla, making the repairs himself and rejecting the suggestions of the others. Seven criticizes Kim's overly hands-on and dismissive approach to commanding the crew, but Kim proceeds to order the ship to resume course. The cloak soon fails again, and six Annari vessels swoop in and fire upon them. While Seven tries to get the cloak back on-line, an explosion in Engineering knocks her unconscious. Kim tries to leave the bridge, but the crew insists he stay, so he lets Dayla go down to Engineering while he gives her instructions over the com. As he's doing that Loken suddenly interrupts and gives Dayla different orders, which succeeds in re-engaging the cloak. Kim eyes Loken suspiciously as he orders the ship to escape at full impulse.
Later, Loken reports that Dayla is dead while Kim tries to treat the still-unconscious Seven. Kim tests Loken by asking his advice as a doctor, having realized that he knows a lot more about cloaking systems than he does biology, as did Dayla. He presses Loken for the truth, and the Kraylor admits that he and his colleagues have not been developing vaccines, but rather cloaking devices for his people's fleet. The so-called medical transport is actually a prototype ship, and the Annari don't want it to reach the Kraylor homeworld. He reveals that his planet has been under an Annari blockade for three years which has been choking off supplies of food and medicine, therefore their mission is still a humanitarian one. Nevertheless, the angered Kim orders the ship to reverse course back to Voyager. But the crew refuses to obey, and Kim realizes he's lost command.
Back on Voyager, Icheb gets flustered when Paris jokes that he's been spending a lot of time with his wife lately. Icheb approaches Torres and tells her outright that they should not be romantically involved. Torres is dismayed, but she plays along and agrees that they should stop "seeing each other."
When Seven of Nine comes to, Kim tells her about the situation and that they should take an escape pod back to Voyager. Seven asks if he's abandoning ship because the mission isn't what he expected, or that being a captain isn't what he expected. In spite of his remorse over Dayla's death, she exhorts him to fulfill his commitment to get the Kraylor home, because they won't survive without him.
As the Nightingale approaches the Kraylor homeworld, the crew sees Annari ships in orbit emitting pulses of energy designed to illuminate cloaked ships. Unsure how they will get through that barrage, Kim comes back to the bridge and promises to find a way.
Voyager receives a hail from the Annari captain who befriended them earlier, ordering Janeway to leave Annari space immediately because they've discovered her people are supporting their enemy. The warp engines are not repaired yet, but Janeway has no choice but to let Voyager be escorted away at impulse speed.
Meanwhile, the Nightingale is detected and gets fired upon by Annari ships. Kim opens a channel to the lead Annari vessel and offers to discuss terms for surrender. He tells his crew to trust him as he proposes to the Annari that they be allowed to evacuate to the surface in exchange for turning over the ship with its cloaking technology, otherwise he'll self-destruct the ship. The Annari commander agrees, but Kim has a plan. Kim, Seven and Terek stay aboard while Loken and the others leave in escape pods. Kim tells Seven to get the exact polarity of the Annari's tractor beam in order to use their own weapons against them. At just the right moment, the Nightingale reverses shield polarity and snaps free, heading for the Kraylor defense perimeter. They outrun the Annari and get through the planet's shield grid, and the Annari break off pursuit. Kim orders Terek to take them to the surface, completing his mission. Back on Voyager, Kim notes in his log that although the mission was a success, he doesn't feel entirely good about it, and he confesses to Neelix that he's not a captain ... not yet, anyway.