Hi! This was written for the Alternate Songs 2017 exchange, and it was written for Dialux on AO3! I really hope you like this! :D Have fun!

Sorry for any mistakes and typos - English is not my first language! And of course, I do not own A Song of Ice and Fire :)

Great Houses carried the ancient blood. Blood touched by the Gods – whose, it depended on who you asked. But so, with every child born into these nine families, a mark, clear as day, appeared on their wrists, a House Sigil (or often enough, an empty circle appeared, to some symbolized no soulmate, but others suspected it meant a soulmate with didn't belong into any of the Houses, either small or great).

It was snowing when Eddard Stark was born, with a very small leaping trout on his wrist. It was sunny, with a small breeze, when, after hours in labour, Catelyn Tully was born with a roaring direwolf on her wrist. Hoster waited a fortnight, just long enough for his wife to recover, before crafting a letter to Winterfell, wanting to promise his daughter to the Stark heir, just a few years older than Catelyn.

Rickard Stark proudly took the letter sealed with the Tully sigil the Maester gave him. Lyarra smiled even more, when she saw the sigil, only wishing for her son to be happy, and to be able to find out his soulmate.

The letter was not what they expected. Lord Hoster of Riverrun offered his daughter's hand to Rickard's heir, to Brandon and not Ned.

"You can't accept this, Rickard. Do not take this girl from Ned."

"It could not be her. Marrying Brandon into a Great House would be very good for Winterfell."

"She has a Stark sigil. We can't risk this," Lyarra reminded her husband. "Write him back, and tell him about Ned."

Lord Hoster was disappointed when he finally read the letter. The Starks offered their second son to his first daughter, not a proper offer, but it could be smart – Catelyn was his heir so far, and hopefully not forever, but she would be able to stay here with this arrangement.

Minisa smiled, just like Lyarra had.

"She has a confirmed soulmate, my lord."

"He is a second son. And we don't know. It could be for a next daughter."

"Catelyn can't be for the heir. They would have mentioned the tattoo on his wrist if it was hers."

Hoster still wasn't convinced after this, and the letter he sent back to the Starks wasn't what they had expected. The Lord of Riverrun didn't promise his daughter to the Eddard Stark, but he promised not to consider any other marriages before talking with Winterfell again.

So Eddard Stark and Catelyn Tully grew up. Eddard became Ned, and Catelyn became Cat. And while not betrothed, they were connected forever. Catelyn was the first one to notice the mark and ask her parents about it; she had been just a bit over two years old, and she went to her septa, pointing at her wrist confused, and then she was brought to her mother.

Lady Minisa put her daughter on her lap and held her daughter'sr arm, clearing her skin, to see the little direwolf.

"Okay, baby Cat, this is a direwolf, and this is the sigil of the Starks, who live up North, they live in the snow – all surrounded by white."

"Snow," Catelyn mumbled, "Diewolf"

"Direwolf," Minisa repeated, but knowing that Catelyn couldn't exactly pronounce the 'r' at her young age. "And this pretty direwolf means there's this boy in the North that the Gods believe that belongs to you."

"Boy." Catelyn smiled.

Although Ned noticed the mark when he was young too, he took a long time to ever ask anyone. He asked Brandon first, but his brother was as confused as Ned, especially that when looking at his own wrist, there was only a white mark.

Finally at seven, and after hearing rumours when he was in the kitchen looking for sweets for him and Lyanna, Ned went to his father. Ned was nervous, but held himself high as he entered his father's solar.

"Come in, son," his father greeted him. "Do you need something, Ned?"

"I wanted to talk to you, Father."

"Okay, come here," Rickard called for his son, and Ned sat on his mother's chair. And then he pulled his sleeve up, unwrapped the cloth on his wrist, and showed it to his father; he wasn't sure what to actually say, but his father picked up on it.

"It's a soulmate mark, son. Do you recognize the sigil?"

"It looks like the Tully trout," Ned answered – he was good with his Houses.

"It means that your soulmate – the person you belong with and should marry – is a Tully."

"So what does Brandon's wrist mean?"

"We don't really know, son."

"But I'll marry a Tully?"

"You should," his father told him. "Lady Catelyn, the oldest daughter of Lord Tully, has a direwolf on her wrist – the Gods believe you belong together. But her father hasn't yet given her hand away."


"For no reason for you to worry about," his father told him, ruffling his hair. "But you'll probably get to meet her soon. As you know, after your next birthday, you'll go and be fostered in the Eyrie – you'll be closer to Riverrun there, maybe you'll get to travel."

Ned wasn't sure what to wait for in the Eyrie. Father told him that there would be another boy his age being fostered there – a Baratheon from the Stormlands. But the Vale was so far from home; Brandon got to be fostered in Barrowton and visit home every other moon, but not Ned. Ned would be lucky if he came home once a year, and he knew he would miss his parents and siblings.

"Don't be nervous, Ned. Your soulmate will love you; and fostering will be good for our family, and for you – boys should be with boys their age, and Lord Arryn will be a great teacher to you."

Ned just hoped that his father's words would prove to be right, both about his time at the Eyrie, and about what would come for him and Catelyn next.

Finally, at age twelve, Catelyn was betrothed to Ned Stark, a second son, and in turn her younger sister, Lysa, was betrothed to the heir of Winterfell, Brandon. Lysa got her letter first, and she carried around her letter around for an entire moon, living of the nice words and promises Lord Brandon had made to her. Catelyn got her letter too, she expected something as nice as Brandon's, after all it was her soulmate on the other side, but she got nothing but a respectable introduction.

Catelyn didn't want to cry that night, so she didn't – she told herself it wasn't worth crying for. Instead Catelyn went to the Sept, and prayed to the Maiden, that she would be happy with him.

The next day, Catelyn and Lysa wrote their letters. Lysa blushed the entire time, and giggled as she told Brandon about the Riverrun and everything she wanted to show him. Catelyn looked at the empty parchment, not sure what to say, so she ended up not differing much from what Ned had written – a simple introduction of who she was. When Lysa gave her the letter to read, Catelyn felt her own was too simple, but she kept it that way; and that evening they gave it to the Maester and they send it out together.

Then Catelyn realized something – Brandon's letters weren't all they seemed to be. Lysa was always enchanted when she got one, but as she waited she cried about how he didn't care and took to long to answer (Petyr would always comfort her then). Eddard's letter came as soon as she sent hers off – he didn't have a way with words like Brandon, but he was reliable, and she could count on him to always be there for her.

Over the seven years they were betrothed, they learned about each other. On their wedding day, Catelyn could name each one of Ned's favorite people, places, foods and things to do in the world, and the same could be said for him. Lysa instead knew that Brandon was fun, handsome and charming, and she thought she loved him by the day they were supposed to marry. The visits between the two pairings were also different: Lysa and Brandon had always escaped somewhere and shared a few kisses, while Ned and Catelyn had never been without a chaperone (even if the chaperones had often allowed a bigger distance, that let the couple have more personal conversations), until their wedding day.

The day turned out not to be what they planned. Actually it turned out to be what Lord Hoster had wanted in the beginning. The Gods had a way of playing with destiny.

When Ned finally arrived to marry Catelyn – he was the heir to Winterfell. Catelyn had thought she would be the lady of a Small House her entire life, now she would be the Lady of a Great House.

Lysa cried. Catelyn tried not to smile. And Ned was uncertain about everything, until Catelyn pulled him away, finally alone she brought him to her arms, and he felt just a bit better.

"I'm really sorry, Ned. I can't imagine what you're feeling…"

"Today should be a good day," he said, holding tightly to her hand. "But everything is… I'm not ready for this, Cat. We were going to have small holdfast, near the Neck and the river… and now…"

"Now you'll be the Lord of Winterfell, and you'll be good," she said, holding his face. "You care for your people. That's all that matters."

"Thank you," he said, resting his forehead on hers. "I'm glad you will be there for me, Catelyn." She smiled, and despite the situation, Ned did one of his very small smiles as well (and he then felt guilty about it).

"I'm sorry, Ned. Don't…"

"Gods, we should be happy… Why did?" Ned murmured, "I want to kill Rhaegar and the Mad King... I just don't understand why he had to take her. Why had Brandon have to go in there? Why had Dad need to…"

"Ned… breathe," she said, kneeling in front of him.

"You know if Brandon came in here now… he would… I would yell at him and…" Catelyn blushed and sat back next to him. "Sorry, Catelyn, I didn't want to…" he apologized.

"I wish I could hear your brother's inappropriate jokes again too."

"How's your sister, Lysa?"

"She can't stop crying. She hasn't stopped since the news came. Every moment I feel I should be with her. We should both be getting married tomorrow – side by side," Catelyn said – she couldn't imagine the pain Ned, and even Lysa, were feeling. "And Father is talking about marrying her to another Lord to secure the war. He's talking about Lord Jon Arryn; I told him he was too old for Lysa – I'm sure he's a great man, but Lysa…"

"Lysa dreamed of Brandon, a charming young man," Ned said. "And tell your father that I won't accept his soldiers if he marries her to someone else."

"You need them," she said.

"I'm hoping your father will listen to my threat."

"Thank you, Ned, you don't need to…"

"We're a team," he reminded her. "But we should go back. I don't want your father to think."

"He trusts me, but we should." Catelyn took Ned's arm when he offered, and they walked back to the castle. There were tents all over the grounds of Riverrun – Stark, Baratheon and Arryn men were sitting around, drinking, celebrating before they left for the war, a few days after the wedding.

As they were closer to the castle, Ned left her to go on alone, needing to meet with his war council that included her father and uncle. Catelyn took a few deep breaths, before making her way to Lysa's room, knowing her sister needed her, and there she stayed for the night.

The next day, Catelyn broke her fast in her room with her father and Edmure, and they all felt that empty space left by Lysa's absence, and the threat of the upcoming war. After an awkward meal where only Edmure broke the silence, Catelyn got ready for the wedding. Every second of the way, she missed Lysa; they were supposed to be getting ready together, but Catelyn was here alone with her maids – while they were more than prepared to dress her, they weren't her sister.

After her dress was ready, with her blue and red cloak over it, her hair pulled up in an intricate hair-do, even if she had wished to wear it down, since Ned had once been brave enough to tell her that he really liked it that way, but it wasn't proper. And then the final touch, for the first time in years, Catelyn disrobed her wrist and showed the mark in front of other people.

The septon came to bless her mark as it was tradition for soulmate weddings in the South. And even if Ned had agree to marry under the Sept, Ned had abdicated of this tradition, but he had gone to their small Heart tree to see his Gods, and make a similar promise and offer thanks to the Gods for this blessing.

Catelyn repeated the words of the septon and the Gods, and only then was her father authorized to enter to take her to the Sept. She met Lysa on the way, and Catelyn was without words at seeing her – she didn't think her sister would come.

"I love you, Cat, I want to try. I love Brandon, as I know you love Ned." Catelyn knew that she could come to love Ned if she didn't love him already. "And I need to be there for you, I need to try," Lysa promised her.

Lysa was dressed in black. Lysa hated black she had probably only used it once before, when Mother died. But besides black, there were touches of grey and white, honouring the Starks.

"Petyr and Edmure will keep me company." Lysa took Catelyn's hand and walked with her and their father, and the moment they entered the Sept, tears came to her sister's eyes, and she found a seat on the sidelines.

Ned stood between the Father and the Mother, and for the first time his mark was disrobed as well, as she came closer she identified the image of a leaping trout. Her father squeezed her hand, and gave her away, and Ned accepted her hand, their wrists and marks were made to touch each other as they were bonded in cloth, and were asked to repeat the septon words – Catelyn had already memorized them, and Ned tried to keep up and at the same time he was able to change it in a way that fit his Gods.

With the promises done, Ned and Catelyn were declared husband and wife, and kisses and cloaks exchanged between them; just before Catelyn saw something strange – a small twinkle in the eyes of each of the Seven Gods, even in the eyes of the Stranger, it was like a proud wink or smile. They celebrated another successful match brought together (the Gods always focused on the good, and not that once again the marks were leading to another war).