The historical development of vaginal reconstruction in vaginal atresia is reviewed. Two more recent indications for vaginoplasty are (i) total pelvic exenteration for carcinoma; and (ii) sex conversion in trans-sexuals. The operations available for these conditions are discussed, with particular emphasis on sex-conversion techniques. A method of vaginoplasty in inadequately treated transsexuals, using random medial thigh flaps, is presented with illustrative case reports.