The two met way back in 10th century, when Klaus along with his siblings, were aided to Count de Martel's castle, after they just became vampires.
Niklaus and his siblings, which include Rebekah, Kol, Finn and Elijah, disguised themselves as Nobles in order to hide from plain sight. Aided to Count de Martel's castle by Lucien, who was a servant back then, Aurora immediately caught Klaus' eye, which annoyed her brother Tristan, as he knew that nothing good could come from a man like Niklaus.
As Klaus and Aurora were slowly falling in love with each other, Tristan's hatred towards Klaus grew.
At some point, Klaus' brother Elijah turned Tristan into a vampire, thus making him the first turned vampire from Elijah's sireline.