These two haven't been on-screen together much, but when they are, it's dynamite. They first meet in "Sleepless," when Mulder's new partner tags along when he goes to talk to Scully about an autopsy. Scully is matter-of-factly tossing organs around while Krycek is trying not to barf. Scully seems a bit resentful; she pretty much ignores him, and refuses to shake Krycek's offered hand. (Admittedly, that was probably a kindness, since she was cutting up a body at the time, but still, she was very curt with him.) Later, when Mulder says that Krycek is okay, Scully seems jealous.
In "Duane Barry," poor Alex makes the mistake of telling her to calm down, and she snaps his head off.
In "Anasazi," she saves Krycek's life by shooting Mulder, who is about to kill Krycek.
In "Tunguska," she might have saved his life again; Mulder appears to be about to shoot Krycek until Scully stops him by calling his name. (Scully says Krycek is "a liar and a murderer" in this episode, but she's about the only person who doesn't beat him up!)
Perhaps most importantly, Krycek is partially responsible for Scully's abduction, and her sister's murder. Much is made of the fact that Krycek may have given Scully's address to Duane Barry, allowing him to kidnap her, but upon careful consideration, this is ridiculous. People's addresses, even FBI agents', aren't generally secret. She's probably listed in the phone book. And even if she isn't, CM could simply have looked her up in the FBI database - the one Scully used to find Marita Covarrubias' address in "Tunguska." If anyone has access to this info, it would be him! However, this doesn't let Krycek off the hook; he did tell CM (at the end of "Sleepless") that Scully was a problem. Presumably that's why they decided to kidnap her - though Krycek may have had no idea how far they were willing to go when he made that report. (It's clear from the conversation Krycek and CM had in the car in "Ascension" that Krycek was not told what they were planning to do about Scully.)
And while Krycek did not shoot Melissa Scully, he was there when she was shot. He didn't report it, so he's at least an accessory to her murder. Apparently, Krycek and Luis Cardinal were sent to kill Dana, and Cardinal killed Missy by mistake. Probably Krycek had no choice in the matter - he was a peon who had to do what he was told or forfeit his life - but involvement in the murder of her sister is not something that Dana Scully will easily forgive, no matter the circumstances.
However, it looks like she never found out. In "Requiem," she works with Krycek, along with Mulder.