The African fish Nothobranchius furzeri is the shortest-lived vertebrate species that can reproduce in captivity, with a median lifespan of 9-11 weeks for the shortest-lived strain. There exist several natural populations of N. furzeri that display differences in lifespan, aging biomarkers, behavior, and color, which make N. furzeri a unique vertebrate system for studying the genetic basis of these traits. Here we report a first generation microsatellite-based linkage map for N. furzeri that allowed us to identify loci linked with tail color and sex. N. furzeri linkage map was generated by genotyping the F2 progeny of a cross between a short-lived, yellow-tailed strain and a long-lived, red-tailed strain. The map contains 25 linkage groups and has a total length of 1012 cM. We identified one region linked with the yellow/red tail color that maps close to melanocortin 1 receptor (mc1r), a gene involved in pigmentation in several vertebrate species. Analysis of the segregation of sex-linked markers revealed that N. furzeri has a genetic sex determination system with males as the heterogametic sex, and markedly reduced recombination in the male sex-determining region. Our results demonstrate that both naturally-evolved pigmentation differences and sex determination in N. furzeri are controlled by simple genetic mechanisms and set the stage for the molecular genetic dissection of factors underlying such traits. N. furzeri linkage map will also help analyze the genetic architecture of traits that characterize this group of vertebrates, including short lifespan and adaptation to extreme environmental conditions.