AU: Anastasia/The Avengers Crossover.

A/N: This is my first Avengers fanfiction! I was listening to the song "Once Upon A December" (OST from Anastasia) and I just couldn't shake this idea from my head. Hope all of you will like it.

*I fucked with the timelines and took liberties with the characters to make the plot more believable. :D

Part 1

Peterhof Palace

St. Petersburg, Russia

Mid-November

Clint tugged at his collar irritably. He hated tuxedos. He didn't care that it was personally designed by Tony Stark's favorite tailor (some guy named George - Army or whatever). They were stuffy, restricted his movement, and made him look like a goddamned penguin. Unfortunately, it was a necessary evil. Situations sometimes called for him to be present on the ground and if he was on the ground, he needed to blend in. He sincerely hoped that tonight wasn't one of those nights. He cracked his neck as he settled into a more comfortable position. After scoping the palace the night before, he had found an unused balcony in the uppermost floor that gave him a perfect view of the grand ballroom.

He frowned at the sight of burn marks on the marble railing before remembering that this place had been engulfed in flames some twenty years ago. The fire had killed quite a number of the palace's residents. He shook his head. Death by fire was probably one of the most painful ways to die.

"Do we have a visual?"

His partner's voice filtered into the comm. link in his ear. He easily found her moving slowly through the crowd, captivating more than a few of the male guests. She was swathed in a plum-colored number that accentuated her figure. The gown might fit her like a glove but Clint knew that more than one weapon was concealed underneath that pretty exterior.

"Not yet." He responded. "I must say, you look good in purple, Romanoff."

"Your fascination with the color never ceases to amaze me."

"Hmm, I'm beginning to think you picked that dress just for me."

"Your ego is inflated enough already."

"So it is for me!" He crowed. He grinned as she rolled her eyes. She began to make small talk with a woman in too much rouge, introducing herself as Anya. Clint allowed himself to relish in the sounds of her lilting Russian. She had been teaching him for quite some time and although he had no difficulty understanding the language, he still had trouble speaking it.

The entrance doors swung open to reveal a middle-aged man in an ill-fitted suit. He was alone. Several of the guests situated nearby greeted him respectfully. Clint scanned the area for any sign of suspicious movement. There weren't any. He didn't think there would be. His presence was welcomed in the palace after all. "Our target has joined the party. He's at your six."

"Protection detail?"

"None."

Natasha nodded subtly before excusing herself from the conversation she had been holding with a polite smile. She proceeded to stalk her prey. Clint fingered his bow in anticipation.

Gregori Efimovich, popularly known as Rasputin, was a controversial figure in Russian society. Despite being an advisor to the royal Romanov family (who were the hosts of tonight's festivities), there were rumours that he was only using them for political advancement. Monarchy may no longer exist in Russia but the Romanov dynasty still held quite an amount of political power. It helped that they were widely loved by the masses. Unbeknownst to the family, however, Rasputin was an underground human trafficking kingpin that had crossed SHIELD's radar several months ago. They had been tracking his activity since then and the Council subsequently placed him on the international threat list.

Clint wondered how the Romanovs would consider a man who looked like Voldemort's hairy twin trustworthy. Long black hair, long black beard, beady black eyes. "I think you should trade that knife for a shaver." He commented dryly.

"We're not here to give him a makeover, Barton. He's heading for the staircase. Looks like we're taking this upstairs."

"I'll meet you there."

Clint exhaled a sigh of relief. He'll be getting out of this monkey suit sooner than he expected. One man versus the Black Widow alone in an empty floor with no panicking stampeding crowds was going to be a walk in the park. He wouldn't even need to get his hands dirty. He'd just have to enjoy the show. He slung his bow across his chest and made his way towards the staircase. He passed ornate walls adorned by old paintings. There were landscapes, portraits, and what he suspected to be pictures of the royal family. He may not be an art expert (that was more of Steve's thing) but he could appreciate them just the same. It was evident that they were all done by a talented hand.

"Which floor are you on?"

"Fourth."

He was almost at the staircase when a faint scream reverberated from below. He broke into a sprint, thundering down the carpeted marble steps with an arrow nocked and ready. An elderly woman with silver-grey hair done in an intricate style had both hands on her chest. She was pale as a sheet as she stared at the scene before her. He had loosed an arrow even before he reached the bottom of the stairs.

Rasputin fell to the ground with a loud thud, the serrated knife falling from his grip. Clint was horrified to see blood on the blade. Natasha's blood.

In a blink of an eye, Clint was catching Natasha as she doubled over in pain. He gently lowered her onto the floor. Her back was bleeding profusely. He cursed under his breath. "We need med evac now." He hissed into his comm. as he ripped out a piece of fabric from his pant leg.

"Dispatching a team now. Status?"

Maria Hill's voice was asking from the other end.

"Target has been eliminated. Widow has a stab wound in the back. Might've punctured a lung." He glanced at the woman on his left. She had not moved an inch. She seemed to be petrified. "And we have one witness."

"Be there in 5 minutes."

Fury was going to give them hell for this, especially since the witness was looking exactly like the Dowager Empress Marie.

"Natasha?" Clint whispered, refocusing on his partner. Her eyes were fluttering shut. Blood continued to seep through the makeshift pressure bandage he had applied onto her back. "Stay with me, Tash."

SHIELD agents poured into the hallway just as she lost consciousness. He released her to the medical team, quickly relaying her status. Rasputin's corpse was slipped into a body bag and carried out to the jet he knew was hovering outside. All this happened in under three minutes. Maria Hill suddenly appeared beside him. She looked pissed. "We'll talk about this later. I'll deal with the witness. Go."

Clint nodded brusquely.

He shot one last glance around the hallway wondering what the fuck had just happened. The Black Widow against one man was supposed to be child's play. He wasn't even supposed to get his hands dirty. But now they were covered in her blood. His tuxedo wasn't faring any better. He decided to shred the damned thing when he got the chance.

He was sitting by Natasha's bedside in the infirmary when he was called to the Director's office. She had yet to wake. Fortunately, the knife had missed the lung and the doctor guaranteed her a full recovery within the next few weeks. Until then, she was required complete bed rest. Although knowing Natasha, it would only take a few days before she got cabin fever and tried to escape.

Fury had a frown on his face when he walked in. Then again, Fury always had a frown on his face. Clint mentally prepared himself for a telling-off that seemed to be a staple in debriefings with the Avengers but never with the Barton-Romanoff duo. The Hawkeye-Black Widow tandem had an almost clean record. They never fucked up. Which was why Clint was expecting a full-on rage-fest from the Director.

To his surprise, it never came.

"So, what happened out there?"

Like they were discussing last night's football game or something.

Clint shrugged. "I'm not really sure sir. Rasputin came in alone. Agent Romanoff followed him to the fourth floor where they apparently engaged in combat. While he might know basic self-defense, he should have been no match for the Black Widow."

"Then what the fuck happened!"

Ah. There's the rage-fest.

"I'm afraid only she can answer that question, sir."

Fury inhaled deeply. He flipped through a manila folder and tossed it towards him. The word CLASSIFIED was stamped on the cover. "I want you to go back to the palace and find out what the hell went wrong."

"Sir?" Clint was confused. Agents fucked up all the time but no one was ever sent back to figure out what went wrong. It was a waste of time and resources.

"You and I both know that the chances of Agent Romanoff telling us what went wrong are very slim. What do you know of Agent Romanoff's past?"

Clint knew a bit of Natasha's past but he wouldn't claim to know everything. He knew that her parents died in a fire when she was around six or seven. A man had reputably rescued her and introduced her to the Red Room. He knew that she defected and later worked as a contract killer, making a name for herself and ultimately landing on SHIELD's radar. The rest, as they say, is history.

But Clint didn't really care about the past. He preferred to stay in the present. And he would be lying if he said that he didn't enjoy peeling away all the layers that was Natasha Romanoff. The trust was there but it was nowhere near completion. There were still skeletons in each of their closets that weren't quite ready to see the light of day.

"Not much, sir."

Fury raised an eyebrow but didn't say anything. "We've had our suspicions before but -" He sighed and gestured for Clint to open the folder.

He made quick work of it. By the end of it, he couldn't help but blink owlishly for several long seconds. "This can't be true, right? I mean, they found the body. All evidence suggests that it was her."

"Yes. But we have to remember that this is the Red Room we're dealing with here. They're very efficient in covering their tracks."

"Then why not do a DNA test?"

Fury shot him one of those 'do-I-look-like-I'm-stupid' looks. "That was the first thing we did. It came back negative."

"Well, there you go." Clint spread his arms wide. "What more do you need?"

Fury fixed him with a steely gaze. "If you can recall, the Red Room injected her with a serum. It could have messed with the tests. What happened last night, was no coincidence. Agent Hill has already briefed the witness on the incident regarding Rasputin. She was apparently very grateful for your intervention and is open to meeting you. Deal with this, Agent Barton. And not a word to anyone. You're dismissed."

Walking through Peterhof in plainclothes with no assassination on the itinerary should have left him feeling a lot more comfortable than before, yet Clint couldn't shake the uneasy feeling in his chest.

One of the maids, a plump woman by the name of Sophie, escorted him through the Royal Palace babbling energetically in rapid-fire French. It appeared that the Dowager Empress had lived in Paris during the restoration of their home in Russia. Clint resisted the urge to groan. He barely understood French. So he opted to just nod and smile at regular intervals.

They arrived at a cozy sitting room with walls lacquered in pale blues and yellows. The furniture was white and supremely elegant. A fireplace burned merrily in one corner. Soft music emanated from a tiny musicbox. It reminded him of a lullaby.

"May I present ze Dowager Empress Marie!" Sophie announced in heavily accented English.

"A pleasure to meet you, ma'am." Clint greeted politely. Inwardly, he cringed. Ma'am? He sounded like Steve. But he didn't really know what to call Empresses.

"Please, call me Marie." She responded in near-perfect English. "Take a seat, Monsieur Barton. Tea?"

"Just Clint, thanks." He said in turn as he took a seat opposite her. "And tea would be lovely."

She smiled as Sophie poured them a cup each. It smelled strongly of lemon. Clint toook a moment to analyze her. She must have been stunning once upon a time. She had all the features of an aristocratic face, thin lips, sharp cheekbones and an even sharper gaze. "Your co-worker, Ms. Hill had informed me that you are here to check on my well-being?"

Clint felt a twinge of guilt even as he nodded. Nope, just here to grill you on your dead granddaughter.

"I must thank you for removing that vile creature from our family. I always had my doubts about him but my son, Alexander, never listens."

Clint nodded again as his brain recalled the contents of the manila folder. Four sons, Nicholas, Michael, George, and Alexander. Only one had survived. Alexander and his family had been with Marie in Paris when the incident had occurred. She began small talk on her two grandsons who were apparently around Clint's age. She made no mention of the one he came to hear about.

Clint decided to just throw it out there. He didn't have all the time in the world. Natasha was going to wake up soon, probably already was awake, and he can't go back without knowing the truth. "I apologize beforehand if this will bring back any painful memories, but I must ask about your youngest granddaughter."

"Ah." Marie's eyes turned distant. He vaguely noticed that they were almost the same color as Natasha's. "Your partner has told you then. I hope she is well?"

Clint shook his head slowly. "I'm afraid she hasn't told me anything. She's healing but she's still asleep."

Marie laughed daintily. "I must have been hallucinating in my fear. I called her by a different name."

Clint leaned forward in his seat. "What did you call her?"

A sad smile graced her features. "Anastasia."

Clint's mind was whirring as he followed Sophie down a familiar hallway. Their meeting hadn't been very informative. Marie herself had stated that Anastasia had perished in the fire. This was nothing but a simple case of mistaken identity. Yet that niggling feeling in his gut would just not stop bothering him.

How can it be a mistaken identity when Anastasia was only seven when she disappeared - ahem, when she died and Natasha was a woman in her mid-twenties?

And there was the incident with Rasputin. Nothing swayed the Black Widow when she was on the hunt. What happened?

He therefore requested Sophie to kindly escort him to the area of last night's incident. He made some ruse about needing to check the crime scene and that it was standard protocol in their line of work. The Dowager Empress had expressed her regret at not being able to accompany them as she was too old to keep climbing up and down the stairs. She thanked him again and disappeared into her room, taking the still-playing musicbox with her, humming as she went.

They arrived at the fourth floor landing and Clint retraced Natasha's footsteps. He found himself face-to-face with a family portrait of the Romanovs. There were several girls with red hair but only one with eyes gleaming a familiar green. "Sophie? Who is this?" He pointed at the young girl.

"Zat is Anastasia. She 'ad been Marie's favorite."

Of course, it would be her.

"What happened to her?" Clint asked, even if he already knew.

"She died in ze fire," Sophie sighed. "But ze Empress would say otherwise."

What? She never said otherwise! "Really? Why?" His heart began to beat a tad bit faster. He blamed it on the exhaustion. He still hadn't gotten any proper rest yet. Yes, that was it. He was exhausted.

Sophie shot him a curious gaze. "She didn't tell you? A young boy used to work here. I think 'e was one of ze cook's children. His name was Dmitri. He used to play with Anastasia all ze time."

Clint made a gesture for her to continue.

"Well, shortly after ze fire, Marie returned for ze funerals. Dmitri was present as well and he claimed that he 'ad helped young Anastasia escape but that they got separated in ze crowd. He tried to look for her but couldn't find her. It was almost as if she just - vanished into thin air. Poof!" Sophie shrugged with a dismissive wave. "It is a tall tale, I am sure. He was only what, 7 years old? But ze Dowager Empress believed him. She even offered a reward to anyone who could find her." Sophie laughed then. "You have no idea what a nightmare zat was, dealing with all ze fake Anastasias."

Clint nodded weakly. "Yeah, it must've been horrible. Well, thank you for all your help, Sophie, but I'm afraid I must leave. I still have business to attend to." Clint forced a smile on his face as she escorted him towards the exit. She kept blathering about French cuisine but he was no longer listening.

It was a good thing he decided to snag the Dowager's used tea cup before they left the sitting room.

He had hoped it wouldn't have to come to this but he was left with no other choice. Clint didn't give two shits about SHIELD's DNA test. They didn't have the kind of technology that he lived with. What was the point of being friends with a self-proclaimed genius if he didn't call in for favors (tuxedo not included) all the time?

As he made his way to the quinjet, he dialed the familiar number on his personal mobile. "Hey Stark? I need your help.

A/N: Review and let me know how it is! :D