In 2369, Nu'Daq represented the Klingon Empire in collecting DNA fragments that would create a program made by the ancient humanoids who had seeded humanoid life in the Milky Way Galaxy. Nu'Daq originally believed that the DNA fragments comprised the designs for an ancient weapon of great power. When he collected one DNA sample from Indri VIII, he destroyed the planet's atmosphere, killing all life on the planet's surface, preventing any other party from procuring another DNA sample.
Nu'Daq engaged Lieutenant Commander Data in the B'aht Qul challenge , in which Data prevailed effortlessly. Angered by his defeat, Nu'Daq attempted to precipitate a fight with Data, by headbutting him. Data was uninjured, while Nu'Daq was thrown back by the force of the impact, after which Data matter-of-factly described the durability of his skeletal portions involved in the impact.
After the Maht-H'a was disabled by a Cardassian attack, Nu'Daq accompanied the crew of the USS Enterprise to Vilmor II. There, the final DNA fragments were collected by Doctor Crusher and Captain Picard. The program modified a tricorder emitter diode to project a recorded image of a humanoid female expressing encouraging peace and cooperation. Nu'Daq, disgusted with the results of their efforts, remarked that if the humanoid in the recording were not dead, he would have killed her. (TNG episode: "The Chase")