jules verne wrote about submarines before they existed, so that would count as sci-fi. as is any movie based on robots/true ai, or shoes with flamethrowers. technically you could take almost any fantasy story and replace all references to magic and spells with technology and device, or replace only half the references and have the whole flying ships and giant robots in a medieval setting you get in escaflowne..
if it were me writing a story i would do the folowing: in a short frase undeline the most fantastic or unlikely part of the world your creating (like "tiny cyborg werewolf ninja"), and then find some reasonable-ish explanation for it to exist ("japanese make supersoldier combining training tech and magic thingie"), then finally try to build up the rest of the world around the explanation until the original fantastic idea is fully in context and sounds perfectly normal. from there the plot writes itself
just do me one favor, avoid the third act reversal... its been done to death in every medium..