There are a number of great Stony fics from way back in the day before MCU was a thing.  They are often hard to find b/c they are typically not tagged very heavily and the ship wasn’t as popular at that time, so they got less attention.  But, there are some real gems to be found there and a neat look at fandom history.   The authors listed have other Stony works, as well, so please check those out, too.  Here are some suggestions for early fics to check out:

Instant Karma’s Gonna Get You by dorcas_gustine:
Cap is disappointed. Predictably things start to Go Very Bad for Tony.

This Time Tomorrow (where were we) by dorcas_gustine:
Tony goes to see Wanda, and suddenly Steve is alive and there are
Skrulls! Or maybe Tony is just going crazy. Nothing happens in this fic,
until the very end. Seriously. There’s a lot of talking, mostly at
inopportune moments, Tony’s views on the acceptable gifts to give people
are slightly different from everyone else’s and he spends more time
than would seem necessary being (half-)naked. What else is new?

A peopled labyrinth of walls by dorcas_gustine:
It’s New Year’s Day and Steve and Tony get lost in Venice. Oh, and there is sex.

These days, they say ‘making sandwiches’ (or, Oops!) by dorcas_gustine:
Cap and Tony are just giant saps. Mostly Cap.

Google This! by dorcas_gustine:
Ah, the wonders of the Internet!

Welcome to the World of Tomorrow by dorcas_gustine:
The future is bright. And has ball-gags, apparently.

Submission Hold by Letterblade:
“Tony,” Steve says, somewhat gently. “So you’re saying, what, that you like it when I hold you down?”

Off Grid by Letterblade:
Steve and Tony go camping, bears are the greatest threat facing America, and tick tweezers are the best invention of the decade.

Orbiter Dictum by schmevil:
Steve is at the sink, washing the few dishes that pizza for two generates, when he realizes that Tony is in love with him.

Attack/Retreat by schmevil:
Steve and Tony work out some relationship problems.

Sea Stars by Muccamukk:
Steve comes back to life somewhere entirely unexpected; Tony doesn’t
remember being a hero; something is rotten in the province of British
Columbia, and the 2010 Olympics are doomed.

Sex and Identity by Muccamukk (series): Series of connected but stand alone stories dealing with Tony’s secret identity, and how he and Steve negotiate it (or fail to).

And the World Keeps Spinning by Perpetual Motion:
He considers everything he knows.  His keys don’t work.  Bucky’s in his
apartment.  There’s a gun to his head.  He doesn’t have his phone or his
Avengers tag.  “I died.“

T is for Thong by Elspethdixon:
Naked might actually have been slightly less distracting. Tony was…
almost wearing… a tiny, tight scrap of red fabric that most definitely
didn’t hide anything.

The Roughest Day by Elspethdixon, Seanchai:
Steve is in a motorcycle accident, Tony catches a cold, and someone is after the New Avengers.

King of Infinite Space by Elspethdixon, Seanchai:
A villain from Tony’s past comes back to cause trouble for the Avengers.
Maybe it wouldn’t have been so easy, if things weren’t already so
awkward over the events of Execute Program.

I Never by Elspethdixon, Seanchai:
Kang had been defeated, they had four hours to kill before the press
conference, and they were reduced to playing a party game Steve strongly
suspected had been made up by 13-year-old girls.

In a Different Light by marinarusalka:
After an unexpected attack, Tony has trouble dealing with his injuries and Steve has trouble dealing with Tony.

Indestructible Things by mechanicaljewels:
Steve shows Tony a new use for the shield.

Nothing Important Happened Today by thedevilchicken:
Steve’s stuck in a time loop. Sometimes he’s not sure he wants to get out of it.

Betwixt by tsukinofaerii:
Steve is pulled into an alternate universe that could have been plucked
from his nightmares. All he wants to do is get home alive. Tony may have
other ideas.

Keep Your Gloves On by tsukinofaerii:
“Why do you keep making passes at me?” Steve tries to help Tony out and
gets a bit more than he bargained for. Tony just likes the uniform.

Commit by tsukinofaerii:
Steve refuses to be a temporary fling.

Right off the Rails by autoschediastic:
Tony’s still pretty sure the dirty little fantasy playing out in his
head isn’t going to come true. Almost one hundred percent sure.

Flyboy by autoschediastic:
“With wild and crazy abandon,” Tony said, and grabbed him around the
waist to yank him close like a black and white picture hero. “Hold on
tight.”

The Past is Gone (But Something Might Be Found To Take Its Place) by destroythemeek:
With his apartment and life in shambles, Steve Rogers needed somewhere to stay. (Immediately post-Avengers Disassembled)

Indelible by Penumbren:
When an experiment goes awry, Tony thinks he may have found an answer to
his problems and Steve faces something he’s been avoiding for a very
long time.

It’s the Sky that Makes the Ocean Blue by skund: Written for [livejournal.com profile] fictionalknight
for her (belated) birthday prompt of Steve/Tony, explosion, with a bonus
prompt of defenestration (the act of throwing something out a window).
An emergency at the Avengers Tower leads to a revelation, and happy
endings are only in story books.Set in a ‘general comicverse’, or
probably better described as a bastard canon; sampling themes from
Classic 70s Avengers (like Iron Man’s identity being secret), but the
Marvel Adventures Avengers line-up (because it’s the only Avengers I
consistently read, lol).

A Window in the Sky by manic_intent:
Steve hits on a total stranger in Port-Lyautey, much to Bucky’s astonishment.

The Tower of Yesterday by manic_intent:
Tony is the WWII hero waking up in the future.  Iron Man Noir.

Movies, Pillows and Phone Calls, Oh My by Settiai:
Spider-Man walked into the rec room just in time for a pillow from the sofa to come flying straight at his face.

Tomorrow and Tomorrow and Tomorrow by ballpoint:
Steve is on the run from the Ultimates, goes to Stark to see if he knows anything. Finds some sort of comfort instead.

A Face to Meet the Faces that You Meet by valtyr:
Identity porn. AU post Cap’s death in ways that should be pretty obvious.

(sidenote:  all of valtyr’s works are great, please check them out!)

Art of War by valtyr:
Steve Rogers has a brilliant tactical mind, and he’s not afraid to use it.

The World Turned Upside Down by Morgan_Steelgrave:
Captain Steve Rogers of the Continental Army is sent to secure the help
of Iron Man, notorious privateer.  Yes, this means pirates…sort of.