Oh boy, finally gathering the courage to write and post a SQ fanfic. It's daunting and exciting!

I don't even know how I ended up knowing I was shipping this ship, I just know I started looking it up and dived off the deep end and kinda haven't resurfaced.

Basically this story came because I've been listening to A Sky Full of Stars on repeat for days on end and feel like the song fits them.

I hope everyone likes this!

I don't own anything, if I did, this ship would be beyond canon.

Regina kept staring at the navy blue velvet box in her hand, willing her brain to start working again. On her other hand was a stock paper card that had been one of the two items inside the box, lying on top of the other item, placed with great care. Surely this was some sort of prank or joke, for there was no way someone would send her such a gorgeous gift, a necklace with a single silver 8-sided star on it. She supposed the star symbol was related to the printed words on the card, and she glanced at the small paper rectangle once more.

'Cause you're a sky full of stars

It was an enigmatic choice of words, that was certain, but the bigger question was how the box had gotten inside of her locked office when she was one of the few people that had a key to it, the other being…

"Kathryn?" Regina made her way out of her office and into the next room, where her blonde secretary and friend looked up expectantly at her after being called. Regina was stuck for a moment, unsure how to phrase herself.

Kathryn, for her part, noticed the items in Regina's hands, and raising a small eyebrow in confusion, prompted the older woman, "Regina? Is there something wrong?"

"Did you-" No, she didn't want to sound accusatory. With the broken curse fresh in everyone's heads, one wrong move could send the mindless mob to picket her house once more. She decided to try again. "Do you know of anyone else that might have keys into my office?"

The secretary was even more baffled now. Regina should know better than her as to who would have duplicate keys, being the mayor and all. Not to mention she had only been in this position for the past couple of months, ever since the curse broke and no one else had risen to the occasion to work under Regina, considering most of the town was either terrified or pissed off at her. "Not that I know of? Perhaps the janitorial staff?"

Regina had to stifle a scoff. There was no way that Leroy would have done this. He was one of the lead organizers of the mob that liked to decorate her house with rotten fruits and eggs regularly. The unruly dwarf had been one of the worst off during the curse, constantly drunk and jailed. But at the time Regina had only seen red to Snow White's closest supporters, and Grumpy had been at the top of the list, right behind her dim-witted husband Charming, who she supposed ended up getting a kind of blessing being stuck in a coma for nearly three decades. But back to the matter at hand, literally. Kathryn had been talking to her while her thoughts had drifted.

"I'm sorry dear, I missed the last part."

"I said that I don't think they have the key to your inner office." After a beat, she added, a tinge of worry in her voice, "Why? Was something taken?"

Regina shook her head. "No, quite the opposite it seems. Someone dropped this off." She showed her friend the open box and the card.

"Oooh, looks like someone has a secret admirer." Kathryn looked up from the items to smirk playfully at her friend.

Now Regina couldn't hold the scoff in, and replied, "Hardly, this is most likely a prank. You know as well as I do that no one in this town likes me, and especially not in that way."

Kathryn kept her mouth shut, making a noncommittal sound. She knew and believed her friend deserved more, but the one and only time they had ventured to discuss that had led to disastrous consequences, which included a few broken vases and a cracked mirror. It was all courtesy of Regina's emotions powering up her magic to explode the objects nearest her, which were the two vases on her mantel, and the mirror hanging above it. Although neither of them got hurt badly, she and Regina still have the fading scars on their arms from the vase shards flying. Changing the course of conversation to a more safer road, she now asked, "Do you want me to notify the Sheriff's station of a break-in then?"

"No no, that's fine. I'd probably just incite the prankster more if I make them the center of attention."

The blonde nodded, not believing the excuse for one second, but thought better than to counter it and then smiled, "So, are you gonna put it on?"

Here, Regina faltered. She had to admit the necklace was pretty, but putting it on might send the prankster the wrong signal. However, she was never one to back down from a challenge, so with a grin that had the smallest of Evil Queen qualities to it, she nodded. "Yes. Want to help me?"

By the time afternoon rolled around, Regina was ready to tear her hair out. Although she enjoyed her job as mayor, she was certain the citizens of Storybrooke were making sure her workload had doubled, probably to dissuade her from potentially crafting any evil plans now that this curse had fizzed and died. Although it might look like it, Regina wasn't being paranoid. She knew for a fact that there were people actively out to make her life miserable, and if they could get a lucky hit, they would try to end her.

The small town had been divided into four groups once the curse broke. Those scared of Regina, keeping their heads down, mouths shut and hoping they could be spared from anymore drama if they just blended into the background. Such were the timid wallflowers like Ashley and her family, as well as Michael Tillman with his children, among others.

The more dangerous and popular group was furious with Regina, and giving her hell was the least that they could do in retribution. Leroy and Whale were spearheading that movement, sometimes aided by Granny, propping up signs and refusing her service around town. They were actually more subdued now, the culmination having been when they had made a giant protest a month ago, breaking into her home and destroying most of it, vandalizing the rest. She thankfully hadn't been home, and neither had Henry, otherwise she was sure she would've been skewered alive, and her son hurt in the crossfire. Her house was still not fully restored, some parts damaged beyond repair, and no one in town would offer her the professional help she needed to fully renovate it. The rage-fuelled group had been later wrangled by the Sheriff and given a thorough talking to, explaining that their actions were very much illegal, and those caught committing further crimes would be penalized to the full extent of the law, no matter who they thought Regina was. Although they still spat vitriol at her every chance they got, they thankfully respected Emma Swan enough to keep their activities only vaguely illegal.

The third group, led by the insipid Charming couple, was solely focused on getting back home to the Enchanted Forest. They attempted to recruit those from the latter group to join them, knowing their efforts would be better spent working together to find a way home, rather than wasting it on Regina. It was a futile and naive effort but they didn't believe Regina when she said the land was gone, and so they continuously perused what they could to scramble for some sort of method home. Regina let them keep at it and didn't insist. It was probably for the better since, as soon as they were to realize they were stuck for good, they would probably join the enraged likes of Leroy and Granny to make her life in this new version of Storybrooke into a true hell.

The final, and infinitely smaller group was the one supporting and defending Regina, making sure that she wasn't killed every time she was out in public. Kathryn had mercifully forgiven her, and despite having been cursed, she had enjoyed being friends with Regina, now working with her to keep her company and make sure no one came in to the Mayor's office with cruel intentions. Her husband, Jim, had been with those wallflowers at first, but after talking with his wife, now joined her, helping Kathryn and Regina to renovate the damaged house on weekends. The group didn't have many more members, the others being Archie, who saw the good in everyone, even Regina, but she was sure that she could be a three-eyed cannibalistic troll eating the denizens of Storybrooke on a regular basis and he'd probably still try to convince her that they would eventually end up seeing the good in her. Ruby had been a surprise, but later Regina found out that the young wolf preferred life here in Storybrooke much more than the Enchanted Forest, and actually thanked her. Sweet Henry was her #1 fan, after they had a serious and honest conversation once the curse broke, and he saw that she wasn't the monster he had thought she was, no thanks to the book's two-dimensional portrayal of her life. She was still trying to prove herself to him, show him that she had changed and wasn't evil.

The final member of the group was someone Regina had never expected, having been the person the curse inadvertently royally screwed over the most. Emma Swan did everything possible to make sure Regina was safe, keeping her word during the town meeting and arresting anyone who was breaking the law to make her life miserable. Regina had been sure that what the Sheriff had said were empty promises meant to keep everyone in their place, but she kept good on her word, surprising Regina. She had even offered and insisted Regina stay over with them while the house was renovated, also for protection, and now shared an apartment with Emma and Henry. Thankfully Emma no longer lived with Mary Margaret, so Regina didn't have that much trouble fitting in to the new home. She also got to see Henry on a regular basis, without having to set up some kind of visiting schedule with Emma, though she was sure that would eventually surface once her house was fully repaired. If Regina had to be entirely honest, she was glad for the current arrangement, and knew that no one would dare to attack her with the Sheriff around, not that she'd admit it out loud...ever. However, she was sure that Emma's involvement was solely because of Henry's insistence, probably having given her a rousing speech on her role as the Savior and Sheriff to a small town.

Speaking of whom, Henry had just burst into her office, Emma trailing behind quietly, giving a nod to Regina as Henry launched into telling his adopted mother his many adventures in school. The two had decided, with Henry's best interests in mind, that Henry should be accompanied around town to avoid anyone trying to hurt him to get to Regina, and although she knew that Granny and some of the tamer haters would never hurt Henry, some of the angrier parts of group Vitriol - as Emma had taken to affectionately name - which mainly consisted of DA Spencer and his old cronies, weren't above chucking a watermelon at Regina's passing car, nearly breaking the glass where Henry was riding in the front. Since that moment, Emma, Regina, or Mary Margaret while in school, kept an eye on him, the latter only doing it as a favour to Emma.

The town was in chaos, and no one knew what to do.

"It was so cool mom! The rocket flew like 10 feet!" Henry was excitedly describing today's science experiment, soda powered rockets. While Regina listened, she couldn't help but glance over at the other woman in the room, noticing that she looked positively exhausted. Being a one-woman police force in a town holding fairytale characters with a grudge on an Evil Queen was probably never in Emma Swan's life plans. She currently looked like she was taking a power nap in one of the chairs at the far corner, and Regina couldn't blame her for wanting some peace and quiet. She knew that last night, Emma didn't come home until early in the morning, having found out when she was awoken with the door slamming shut, relaxing once she realized it was just the Sheriff.

"So what's up with the necklace mom? Is it new? I didn't see it when we left home this morning." Henry, with unaltered curiosity, smiled up at her as he asked, looking as if he had downed the contents of the pop bottles used for the rockets all by himself.

"Someone gave it to me this morning."

"Who was it? Was it a present forgiving you?"

"No Henry, someone... left it here for me to find it. They didn't leave a name." Regina wasn't too sure how much of this she wanted to tell Henry, but the questions just kept coming, and sneaking a glance at the Sheriff, Regina could hazard a guess that the woman was listening.

"Didn't Kathryn see who it was?"

"No, she wasn't here when this was dropped off."

"So how did it get in here?"

"We think…maybe someone broke in here."

"WHAT?!" Henry practically screamed, and at this Emma woke up, jumping out of her seat as though she had been sitting on hot coals. Apparently the Sheriff wasn't listening as intently as Regina had originally thought.

"What happened?" Emma reached behind her for the gun Regina knew she kept hidden, glancing around for signs of danger, but at seeing the two other occupants in the room sitting calmly, she dropped her hands, the gun still hidden and holstered.

"Someone broke into mom's office to drop off a necklace." Henry replied, looking at her with a smile. Emma looked so silly, hands before on her back ready to draw something out, now limply at her sides, face stuck between surprise and anger at having been rudely awoken from a nap.

"Oh," Emma said, not fully comprehending what happened. Regina supposed that the lack of reaction or surprise to the news was owed to her sleepy state. After a few beats it sunk in. "Wha- wait did they take anything? Did they leave some kind of threatening message-?"

"No, Ms. Swan, merely what I believe to be a prankster with a set of lock-picking tools lacking a sense of humor. The note was harmless-"

"Wait there was a note? What did it say?" Henry was positively beaming by now, curious to know what it said. Emma, although less surprised and insistent, probably still waking up, looked at her expectantly.

"It said, ''cause you're a sky full of stars'" Regina shrugged, not giving much thoughts to the words.

"I think" Kathryn piped up with a smile, coming inside with some coffee for the three of them and a hot chocolate for Henry, "that she's got a secret admirer."

"I hardly think a cryptic note and a necklace is the start to someone serenading me." Regina accepted the coffee with a smile

Emma smirked, sipping her own graciously accepted coffee. "But you're wearing it." Trust the woman to get back to her teasing ways at the smallest of things.

"I think, Sheriff, we should worry more about who broke in and why, rather than whether or not I'm wearing a necklace." Despite Regina's attempts and promises to be better, she couldn't help but snark back at the Sheriff, who easily got under her skin.

Fortunately, Kathryn kept quiet on the fact that just this morning, Regina didn't even want to bother with contacting the Sheriff about this, taking her own coffee to sit on the other side of the room.

"Well I'm not Sherlock Holmes, so unless you've got a secret camera installed somewhere, I'm not too sure I can help you reverse-engineer the scene, unless by some miracle our serenading prankster left prints all over the gift and are intact after you touching it."

Leave it to Emma Swan to not back down from a snark challenge. She really had no idea how it was that the one person who had more balls than half her kingdom, enough to be able to snark at her without fear of being pulverized, had to be the daughter of her arch-nemesis, who was currently protecting her life against a rogue town. Granted she had never truly met her Evil Queen side, but it still stood to bear that she didn't care about who Regina had been in the Enchanted Forest.

But right now, her pride came before her admiration, and she replied, "Well Sheriff, if I had known you'd go all CSI on this hours ago, I'd have been more careful."

Emma gave her a 'really?' look, eyebrows making Regina want to yell at the insufferable woman. "Maybe it'd have been a better idea if you'd reported the break in right away? Rather than a casual mention 'hours later'?"

Here Regina faltered. Kathryn swung to the rescue... or at least tried to. "Well we thought about contacting you, but Regina believed that giving attention to the prankster would fuel him to keep at it."

If Emma's eyebrows could raise any higher, she was sure they'd be above her hairline by now. "Okay, my bullshit meter just skyrocketed, and probably broke. That's nonsense and you both know it." Emma made her way to Regina's desk, her strides with purpose, determined to find out the truth.

Just then, Henry decided he was bored of the back-and-forth dance they always did, and randomly blurted out that he was going to get his game, mentioning he left it in Regina's car. The kid was smart, leaving something elsewhere so he could ditch an intense moment whenever his 11 year-old head got tired of adult banter, but the tactic was getting overused. Still, Regina reached into her desk to pull out the car keys handing it over to him.

When the door closed, Emma rounded once again on Regina. "Okay so, I'm waiting."

"I-" How was Regina to explain that this whole situation made her feel weak? Every time someone glared at her, or set out to do serious damage to her, she was reminded that these people would not stop until she was dead. She knew she probably deserved the persecution and verbal punches. But being powerless to get them to see that she was sorry for what she had done, that she was willing to change, and being forced to take all of this punishment reminded her of Mother's teachings, which made her feel even worse.

'If you let peasants have power over you, let them overtake you, they will use that to their advantage and overthrow you, and a Queen must never allow that to happen. She must also always show she is stronger and more powerful than they could ever be combined. Otherwise she is seen as weak, and Queens can't be weak.'

And worse, to have the Sheriff being the only one between her and the mob was an even crueler twist, the irony going even deeper knowing it was the daughter of her nemesis. But how could she explain that?

Fortunately she was saved from having to answer right away when the door burst open, bringing in an awestruck Henry.

"You guys have to see this!" Without waiting for them, he ran back out.

With a careful glance and Emma, Regina rounded her desk, and followed Emma and Kathryn outside, and towards the back parking lot where her car was parked.

She kept her car out of the public eye, knowing that the last time she left it out the front and main lot, the windows had been smashed. Sure it took more time to get to her car, but it was worth keeping her vehicle intact.

Going outside, ready for anything, she nearly collided onto Kathryn, who was frozen, mouth gaping, staring at where her car should have been parked.

Well, her car was still there, but whereas the surface of her car was black, it was now bright pink. Someone, and Regina could guess that it was the same fool who had given her the necklace she was wearing now, had done this.

"Are those-" Kathryn paused, nearing the car, to where Henry stood with Emma. "Post-its?"

"Yep!" Henry grinned, glancing at his flabbergasted mother.

Regina, for her part, shut her mouth when Henry looked at her, slowly advancing.

The young boy turned back to the car and added, "And not just any post-its, they're heart shaped!"

It was true, the post-its, in 3 different shades of pink, were all heart shaped. Regina made her way closer to the car, and went over to the front side, which had been facing away from where they came in from, to see if it had been covered with the pink hearts as well, and now that she had taken a good look, she gasped.

The other three, hearing Regina's gasp, rushed over to join her.

The hood of the car was covered in more post-its, but here the decoration was different. Whereas the rest of the car had been a random medley of hearts in different shades, here there was a clear design in mind. The person had covered the base with the lightest post-its, and then made a giant heart that covered the width of the hood with the medium shade, and then, there was a single post it smack in the middle, in the darkest shade.

Regina neared it, and plucked it, noting that right underneath it, rather than being the medium shade, it was the light shade. Clearly they had thought it through that Regina taking the heart would still leave the original design intact somehow.

"There's something written on it!" Henry looked at the post-it on her hand, and with a jolt, she hadn't realized that it was indeed filled with words. In silver ink, the words made her own heart jump at her throat.

I'm gonna give you my heart.

"Oh yeah, someone is definitely serenading you."

Well that was the first chapter! I'm sorry if it got a bit too much explanation, but I feel like it's worth explaining things so everyone's aware what the situation is.

So thoughts? Who do you think the serenading person is?

I'm kind of on fire with this story, wanting to keep writing, but I want to see what people think of the story before going at it full speed.

Let me know what you think and I'll be updating the story soon!