Faits: A. Propriétaire de la parcelle n° 9574 (AE) de son cadastre, la commune de Sion l'a divisée le 8 novembre 2010 en deux immeubles: le n° 16'711, qu'elle a gardé, et le n° 9574 (NE), qu'elle a vendu à F._ SA. F._ SA était, jusqu'au 10 juin 2010, copropriétaire des parcelles nos 9576, 9577, 9580, 14681 à 14685, à l'est et au sud du n° 9574 (NE). Ce jour-là, elle a acheté l'intégralité de ces biens-fonds (ci-après: n° 9574 ss), sis au lieu-dit Champs Neufs entre le chemin de Châteauneuf et la rue Oscar Bider et qui forment, avec le n° 9574 un mas de 10'020 m2 en zone mixte (zone M2) au sens de l'art. 95 du règlement de construction et de zones (RCCZ) approuvé par le Conseil d'Etat du canton du Valais (ci-après: le Conseil d'Etat) le 28 juin 1989. Les parcelles nos 9574 (NE) et 16711 bordent la rue des Bouleaux. Le Conseil d'Etat a approuvé, le 28 juin 1989, la carte "plan des zones / affectations" qui indique la zone M2 en violet strié d'obliques noires, en laissant en blanc une étroite bande de terrain traversant la partie nord des nos 16711, 9574 (NE), 9576 et 9580. La légende de la carte précise que ce blanc désigne une limite de zone coïncidant avec l'axe d'une route. Une zone d'habitat collectif B jouxte la bande blanche. Sa réglementation est, en tant qu'elle importe ici, celle de la zone M2. Dans ces deux zones, le Conseil communal peut adopter des plans de structuration et/ou de quartier d'une surface maximale de 10'000 m2, avec un indice maximal de 0.9 en zone M2 et de 1.0 en zone d'habitat collectif B (art. 60 let. d et art. 95 RCCZ). B. Le 1er décembre 2006, le Conseil communal a publié dans le Bulletin officiel un projet de plan de structuration, d'un périmètre de 10'079 m2 regroupant les parcelles nos 9574 ss, y compris la bande blanche. Le projet n'a pas suscité d'opposition et a été approuvé le 21 décembre 2006 par le Conseil communal (ci-après: le plan de structuration 2006). Une demande d'autorisation de construire du 31 janvier 2011 de F._ SA a été publiée au Bulletin officiel du 11 février 2011. L'avis signalait un projet de construction, sur les nos 9574 ss, de six bâtiments d'habitation (104 logements avec stationnement couvert) et une demande de dérogation aux règles sur la distance à la limite. Des propriétaires voisins se sont opposés à l'octroi de l'autorisation de bâtir délivrée le 20 octobre 2011 par le Conseil communal. Le 20 juin 2012, le Conseil d'Etat a admis le recours des voisins et annulé le permis de construire litigieux, au motif que la bande blanche traversant les portions nord des nos 9574, 9576 et 9580 n'était pas affectée à la construction de bâtiments privés. Le périmètre du plan de structuration de 2006 englobait donc illégalement des surfaces inconstructibles. F._ SA a porté sa cause devant la Cour de droit public du Tribunal cantonal valaisan (ci-après: le Tribunal cantonal) qui, par arrêt du 19 avril 2013, a admis son recours et annulé le prononcé du Conseil d'Etat du 20 juin 2012. Les juges cantonaux ont considéré en substance qu'il n'y avait pas lieu de revenir sur la légalité du plan de structuration 2006 et que le projet litigieux respectait la législation en matière d'aménagement du territoire. C. Agissant par la voie du recours en matière de droit public, A._, B._ et C._ ainsi que D._ et E._ demandent au Tribunal fédéral d'annuler l'arrêt du Tribunal cantonal du 19 avril 2013 ainsi que le permis de construire délivré à F._ SA. Subsidiairement, ils concluent à l'annulation de l'arrêt attaqué et au renvoi de l'affaire au Tribunal cantonal pour nouvelle décision. Ils se plaignent pour l'essentiel d'une violation de leur droit d'être entendus et du principe de la bonne foi ainsi que d'une mauvaise application de la législation en matière d'aménagement du territoire. Le Tribunal cantonal renonce à se déterminer. Le Conseil d'Etat conclut à l'admission du recours. La Ville de Sion conclut au rejet du recours et à la confirmation de l'arrêt attaqué. L'intimée F._ SA conclut au rejet du recours. Les parties ont déposé des écritures complémentaires et confirmé leurs conclusions. Par ordonnance du 17 juin 2013, le Président de la Ire Cour de droit public a admis la requête d'effet suspensif des recourants.