Background: Living gnathostomes (jawed vertebrates) comprise two divisions, Chondrichthyes (cartilaginous fishes, including euchondrichthyans with prismatic calcified cartilage, and extinct stem chondrichthyans) and Osteichthyes (bony fishes including tetrapods). Most of the early chondrichthyan ('shark') record is based upon isolated teeth, spines, and scales, with the oldest articulated sharks that exhibit major diagnostic characters of the group - prismatic calcified cartilage and pelvic claspers in males - being from the latest Devonian, c. 360 Mya. This paucity of information about early chondrichthyan anatomy is mainly due to their lack of endoskeletal bone and consequent low preservation potential. Methodology/Principal Findings: Here we present new data from the first well-preserved chondrichthyan fossil from the early Late Devonian (ca. 380-384 Mya) Gogo Formation Lägerstatte of Western Australia. The specimen is the first Devonian shark body fossil to be acid-prepared, revealing the endoskeletal elements as three-dimensional undistorted units: Meckel's cartilages, nasal, ceratohyal, basibranchial and possible epibranchial cartilages, plus left and right scapulocoracoids, as well as teeth and scales. This unique specimen is assigned to Gogoselachus lynnbeazleyae n. gen. n. sp. Conclusions/Significance The Meckel's cartilages show a jaw articulation surface dominated by an expansive cotylus, and a small mandibular knob, an unusual condition for chondrichthyans. The scapulocoracoid of the new specimen shows evidence of two pectoral fin basal articulation facets, differing from the standard condition for early gnathostomes which have either one or three articulations. The tooth structure is intermediate between the 'primitive' ctenacanthiform and symmoriiform condition, and more derived forms with a euselachian-type base. Of special interest is the highly distinctive type of calcified cartilage forming the endoskeleton, comprising multiple layers of nonprismatic subpolygonal tesserae separated by a cellular matrix, interpreted as a trnsitional step toward the tessellated prismatic calcified cartilage that is recognized as the main diagnostic character of the chondrichthyans.