Ephemeroptera (mayflies) is sister to all remaining extant winged insect groups and is, consequently, among the first group of insects to have ever taken flight. Additionally, mayflies are unique by having a non-reproductive winged stage that molts (subimago). This study presents the most complete phylogenetic analysis for Ephemeroptera based on molecular and morphological data. More than 150 genera from all families and major clades are represented. Sequence data and morphological characters were analyzed simultaneously via direct optimization, which produced a robust topology. The clades Furcatergalia, Pannota, Ephemerelloidea, Caenoidea and Carapacea were supported as monophyletic while Setisura (=Heptagenioidea), Pisciforma, Baetoidea, Siphlonuroidea and Ephemeroidea were not supported as monophyletic. The resulting topology was used to investigate evolutionary trends. Mandibular tusks were found to have at least one loss in Behningiidae and possibly two unique origins in the Potamanthidae and remaining burrowing mayflies. The fish-like body form and swimming behavior, typical of the pisciform mayflies, may not have a single origin in mayflies. The medial fusion of wing pads was strongly supported as a synapomorphy for the Pannota. These data support a single origin for the evolution of the notal shield. The mapping of the highly movable gills character on the topology neither strongly supports nor refutes the hypothesis for the pleural origin of wings from thoracic gill-like pleural extensions.