Reliable tools for the identification of genetic sex are invaluable in many fields of biology, but their design requires knowledge of sex-linked sequences, which is lacking in many taxa. Restriction-site associated DNA sequencing (RADseq) is widely used to identify sex-linked markers, but multiple distinct strategies are employed, and it is often not obvious which is most suitable. In this study we compare two approaches for using RADseq to identify sex-linked markers. We use the common newt, Lissotriton vulgaris, as our study system, providing a challenging combination of homomorphic sex chromosomes and an exceptionally large genome. We attempt an associative approach, sequencing 60 adult newts of known-sex individuals, and compare this to a linkage mapping approach utilizing a family of 146 offspring with unknown sex. After optimization for a highly paralogous genome, the associative approach identifies five Y-chromosome linked markers in L. vulgaris and we design a robust PCR protocol for molecular sexing of four more related species. Via the linkage approach we construct a high-density map featuring 10,763 markers, matching the observed karyotype of L. vulgaris and showing broad synteny with the Iberian ribbed newt (Pleurodeles waltl). However, without incorporating the markers identified via the association-based approach, we cannot confidently distinguish a sex-determining region in the linkage map, either by analyzing marker density or by identifying clusters of paternal markers. We conclude that linkage mapping alone is unlikely to yield sex-linked markers in organisms with very small sex-determining regions, however association-based RADseq can still be effective under these conditions.