Það var Vesturfari, Douglas DC-8 farþegaflugvél á vegum Icelandair, þá Flugleiða, sem fór fyrstu áætlunarferð félagsins til Orlandó í Flórída. Þetta var þann 26. október árið 1984 og því eru nú liðin 35 ár frá þessum áfanga. Icelandair var jafnframt fyrsta evrópska flugfélagið sem hóf að fljúga reglulega til Orlandó.
Til að byrja með var aðeins ein brottför í viku og yfirlýst markmið stjórnenda Icelandair var að selja sætin um borð til annars vegar sólþyrstra Evrópubúa og hins vegar skíðaáhugafólks í Flórída. Síðarnefndu hópnum stóð nefnilega til boða tengiflug með Icelandair frá Lúxemburg til Salzburg í Austurríki þaðan sem stutt er í fjölda skíðasvæða.
Orlandó hefur verið hluti af leiðakerfi Icelandair allar götur síðan þó ferðirnar leggist vanalega af yfir sumarmánuðina. Sem fyrr segir var upphaflega aðeins flogið til Flórída frá Lúxemburg en árið eftir jómfrúarferðina hóf Icelandair, í samstarfi við íslenskar ferðaskrifstofur, að bjóða upp á stakar ferðir héðan til Orlandó. Í dag er því komin löng hefð fyrir vetrarferðum Íslendinga til Flórídaskagans.
Núverandi vetraráætlun Icelandair gerir ráð fyrir daglegum ferðum milli Keflavíkurflugvallar og alþjóðaflugvallarins í Orlandó. Þangað flutti félagið starfsemi sína á ný árið 2014 eftir að hafa haldið til á Sanford flugvelli í Orlandó í átta vertíðir.